104. Maximum Depth of Binary Tree

──────────────────────────────────────────────────────────────────────

回傳二元樹的最大深度（從根到最遠葉節點的節點數）。

思路

這題是後序型遞迴的最小範例，樹的中難題有一大半都是它的變形，所以值得把「為什麼這樣寫」講到很清楚。

樹的遞迴只要回答兩個問題：用哪種遍歷、遞迴要回傳什麼給父節點。

這題的答案是：

回傳「以我為根的這棵子樹有多深」。

一旦這樣定義，遞迴式就自己浮出來了 —— 我的深度 = 左右子樹裡比較深的那個 + 1（那個 1 是我自己）。而且必須等左右都算完才能算我自己，這就是後序。

base case 的選擇也是從定義推出來的：空樹的深度是 0，不是 1、也不是 None。定義清楚了，max(left, right) + 1 對葉節點自動成立（兩邊都是 0，得到 1），不需要為葉節點寫特例。

面試時的講法：先說「我讓遞迴回傳子樹的深度」，再寫程式碼。多數人卡住是因為沒先把回傳值的語意定義出來就開始寫。

解題方向

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

把 left 和 right 拆成兩行而不是寫成一行 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1，是刻意的好習慣：一旦題目變成「還要拿子樹的值做別的事」（例如 543. Diameter 要把左右相加），你只要在中間插一行，不用改結構。

補充

同一個骨架的變形，差別只在「拿到左右子樹的值之後做什麼」：

題目	回傳給父節點	答案怎麼取
104 這題	子樹深度	就是回傳值
543. Diameter of Binary Tree	子樹深度（一樣）	左 + 右，用外部變數記最大
124. Binary Tree Maximum Path Sum	單邊最大路徑和	左 + 右 + 自己，外部變數記最大
337. House Robber III	(偷我, 不偷我) 兩個值	根節點兩者取 max

543 和 124 的共同重點是：回傳給父節點的值，和答案要的值不一樣。這是後序型題目最容易卡住的地方，而 104 因為兩者剛好相同，所以是最好的入門。

最小深度不是把 max 改成 min：111. Minimum Depth of Binary Tree 要求到葉節點的最短距離，單邊為空的節點不是葉節點，所以要特別處理，否則會回傳 0。這是很常見的陷阱題。

N-ary 版本：559. Maximum Depth of N-ary Tree，把 max(left, right) 換成對 children 取 max 就好。

整理見 Tree 遍歷模板。

複雜度

時間 $O (n)$ — 每個節點造訪一次
空間 $O (h)$ — 遞迴堆疊，h 是樹高

其中 n 是節點數、h 是樹高。平衡樹的 h 是 $O (\log n)$ ，退化成一條鏈時是 $O (n)$ —— 樹的遞迴題空間永遠是這個答案，被問到就這樣講。