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

題目描述

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

解題思路

遞歸定義：

• 空樹深度為 0。
• 非空樹深度 = max(左子樹深度, 右子樹深度) + 1。

這直接對應「最長路徑節點數」的定義，代碼極其簡潔。

參考代碼 (C++)

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;
    }
};

複雜度分析

• 時間：O(N)，每個節點訪問一次。
• 空間：O(H) 遞歸棧深度，最壞 O(N)（鏈狀樹），平均 O(log N)。

迭代替代方案（BFS/DFS 顯式棧）

若擔心棧溢出，可用層序遍歷（BFS）計算層數，或顯式棧模擬後序遍歷。