LeetCode 104 Maximum Depth of Binary Tree：二叉樹最大深度（遞歸）

問題描述

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

遞歸解法

樹的最大深度 = max(左子樹深度, 右子樹深度) + 1。空樹深度為 0。

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

迭代解法（BFS 層序遍歷）

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

複雜度

• 時間：O(n)，每個節點訪問一次。
• 空間：遞歸 O(h)（棧深度），BFS O(w)（最大層寬度）。

此題是樹遞歸最基礎的練習，也是劍指 Offer 高頻題，掌握遞歸與迭代兩種寫法即可。