104.Maximum Depth of Binary Tree

DFS（深度優先搜尋）

想法：
最大深度 = 1 + 左右子樹最大深度

程式碼：

class Solution {
    public int maxDepth(TreeNode root) {
        // 遞迴終止條件：遇到空節點返回 0
        if (root == null) return 0;

        // 分別求出左子樹與右子樹的最大深度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // 當前節點的最大深度 = 1(自己) + 左右子樹最大深度
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

實際操作：

呼叫 maxDepth(3)

STEP1:
在 maxDepth(3) -> 先呼叫 maxDepth(9)
maxDepth(9): left = maxDepth(null)=0, right = maxDepth(null)=0
=> maxDepth(9) 回傳 1

STEP2:
回到 maxDepth(3) -> 再呼叫 maxDepth(20)
在 maxDepth(20) -> 先呼叫 maxDepth(15)
maxDepth(15): left/right = null -> 回傳 1
再呼叫 maxDepth(7)
maxDepth(7): left/right = null -> 回傳 1
=> maxDepth(20) = 1 + max(1,1) = 2 （回傳 2）

STEP3:
maxDepth(3) = 1 + max(maxDepth(9)=1, maxDepth(20)=2) = 3

結果：回傳 3

—

兩者比較

• 只求最大深度——＞優先用 DFS（遞迴）（簡潔）
• 需要「每層節點」或層級處理——＞用 BFS（層序）