LeetCode Maximum Depth of Binary Tree：遞歸求樹高

問題描述

給定二叉樹根節點，求最大深度（根到最遠葉子的節點數）。

遞歸解法

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

迭代解法（BFS 層序遍歷）

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

複雜度

• 時間：O(n)
• 空間：遞歸 O(h)，BFS O(w)（最寬層寬度）