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

題目描述

給定二叉樹根節點，求最大深度。深度定義為從根到最遠葉子節點的節點數。空樹深度為 0。

遞歸解法

節點深度 = max(左子樹深度, 右子樹深度) + 1。終止條件：root == nullptr 返回 0。

代碼實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

複雜度

時間 O(n) 訪問每節點一次，空間 O(h) 遞歸棧深度（最壞 O(n)，平衡樹 O(log n)）。

迭代替代方案（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(); depth++;
        while(sz--) {
            TreeNode* cur = q.front(); q.pop();
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
    }
    return depth;
}