Maximum Depth of Binary Tree

題目描述

給定一棵二元樹的根節點 root，回傳其最大深度。最大深度是從根到最遠葉節點的最長路徑上的節點數。

解題思路

Base Case

節點為 null 時回傳 0，代表空子樹深度為 0

遞迴左子樹

呼叫 maxDepth(root.left) 取得左子樹的最大深度

遞迴右子樹

呼叫 maxDepth(root.right) 取得右子樹的最大深度

合併結果

取左右較大值再加 1（加上當前節點），回傳 max(left, right) + 1

程式碼

C#

csharp

public class Solution {
    public int MaxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = MaxDepth(root.left);
        int right = MaxDepth(root.right);
        return Math.Max(left, right) + 1;
    }
}

TypeScript

typescript

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

Python

python

def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    left = maxDepth(root.left)
    right = maxDepth(root.right)
    return max(left, right) + 1

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(h) |

n 是節點數，h 是樹高（遞迴 call stack）。Time O(n) 是因為每個節點恰好被訪問一次、做常數操作。Space O(h) 是遞迴 call stack 的深度，平衡樹時 h = O(log n)，最壞（skewed tree，每個節點只有單邊子節點）h = n。

邊界情況

空樹：root 為 null，直接回傳 0
只有根節點：左右都是 null，max(0, 0) + 1 = 1
完全偏斜樹：如 1→2→3→4（每個只有右子），深度等於節點數 4，call stack 也是 O(n)

圖解

3 → max(1,2)+1=3

左→

9 → max(0,0)+1=1

→

20 → max(1,1)+1=2

左→

15 → 1

→

7 → 1

圖表展示了從葉子向上匯總的過程：節點 15 和 7 深度為 1，節點 20 取 max(1,1)+1=2，節點 9 深度為 1，根節點 3 取 max(1,2)+1=3。

進階觀點

💡面試追問

Q: 如何用 BFS 解這題？ A: 用 Queue 逐層遍歷，每處理完一層 level++，最終 level 就是最大深度。BFS 的 Space 是 O(w)（w 為最大寬度），對平衡樹 w 可達 n/2。

Q: 求最小深度（LC 111）和最大深度有什麼差異？ A: 最大深度直接取 max，但最小深度不能直接取 min — 如果某個節點只有一邊子樹，另一邊為 null（深度 0），不能取 0 作為最小深度。需要特判：只有一邊時取有子樹那邊的深度 + 1。

Q: 有哪些常見變體題？ A: LC 111 Minimum Depth（最小深度，需特判單邊子樹）、LC 110 Balanced Binary Tree（每個節點左右子樹深度差不超過 1）。兩題都以 maxDepth 為基礎，稍作修改即可。

理解測驗

🤔 為什麼 base case 是 root == null 回傳 0，而不是回傳 -1？

🤔 一棵只有根節點的樹，最大深度是多少？