LeetCode 104：二叉樹的最大深度——遞歸與迭代解法對比

問題描述

給定一棵二叉樹，求其最大深度。最大深度是從根節點到最遠葉子節點的最長路徑上的節點數。

遞歸解法（DFS）

最直觀的方法：樹的最大深度 = max(左子樹深度, 右子樹深度) + 1。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return 1 + max(left, right);
    }
};

迭代解法（BFS 層序遍歷）

用隊列逐層遍歷，計數層數。

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int sz = q.size();
        depth++;
        while (sz--) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return depth;
}

迭代解法（DFS 顯式棧）

棧存 (節點, 當前深度)，模擬遞歸。

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    stack> st;
    st.push({root, 1});
    int ans = 0;
    while (!st.empty()) {
        auto [node, d] = st.top(); st.pop();
        ans = max(ans, d);
        if (node->left) st.push({node->left, d+1});
        if (node->right) st.push({node->right, d+1});
    }
    return ans;
}

複雜度對比

選擇建議

• 面試首選遞歸：代碼簡潔，邏輯清晰。
• 深度極大（如 10⁵）時用 BFS 或顯式棧，防棧溢出。
• BFS 還可輕鬆擴展求每層節點數、最小深度等。