LeetCode 刷題日記
EP.09

Tree & DFS
遞迴的本質，就是信任自己

#104 Max Depth · #100 Same Tree · #226 Invert — 三題打通 DFS 思維

Joseph Chen
2024
Back to Blog
5 min read
1.2k views

Tree 是 NeetCode 150 裡面被標注「🔥🔥 Super Important」的主題。幾乎所有 Tree 題都可以用遞迴（DFS）解——但「遞迴」對很多人來說是個謎。這篇用三道題，把遞迴的思維方式說清楚：你只需要定義好「這個函式做什麼」，然後信任它對子節點也成立。

Binary Tree 的結構

每個節點最多有兩個子節點（left 和 right）。沒有子節點的叫葉節點（Leaf）。

3
9
left
20
right
None None
15
7
Python 的 TreeNode 定義（LeetCode 固定格式）
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

DFS 遞迴的思維方式

寫 Tree 遞迴題時，很多人的錯誤是「試圖在腦中追蹤所有層的執行過程」——這是不可能的，也不需要。

正確的思維：

1
定義清楚：這個函式「對一個 node」做什麼、回傳什麼
2
寫好 base case：node 是 None 時怎麼辦
3
假設：左子樹和右子樹已經得到了正確答案（信任遞迴）
4
組合：把左右子樹的答案組合成當前 node 的答案

#104 Maximum Depth of Binary Tree

一棵 Binary Tree 的「最大深度」= 從 root 到最遠葉節點的層數。

Input / Output
3
    / \
   9  20
      / \
     15   7

Output: 3   ← root(3) → 20 → 15 or 7，共 3 層

套入思維框架：

1. 函式定義maxDepth(node) 回傳以 node 為根的子樹最大深度
2. Base casenode 是 None → 深度是 0
3. 信任遞迴左子樹深度 = maxDepth(node.left)，右子樹深度 = maxDepth(node.right)
4. 組合答案當前節點的深度 = max(左深, 右深) + 1（加上自己這層）
#104 Maximum Depth of Binary Tree
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:            # base case
            return 0

        left_depth  = self.maxDepth(root.left)   # 信任左子樹
        right_depth = self.maxDepth(root.right)  # 信任右子樹

        return max(left_depth, right_depth) + 1  # 組合 + 自己這層
⏱ Time: O(n)💾 Space: O(h) h=樹高，遞迴呼叫棧深度

遞迴展開過程（上面的範例）：

maxDepth(3)
→ maxDepth(9) = max(0,0)+1 = 1
→ maxDepth(20)
→ maxDepth(15) = max(0,0)+1 = 1
→ maxDepth(7) = max(0,0)+1 = 1
→ maxDepth(20) = max(1,1)+1 = 2
→ maxDepth(3) = max(1,2)+1 = 3 ✅

#100 Same Tree

判斷兩棵樹是否完全相同（結構和值都一樣）。

Input / Output
p:    1        q:    1
     / \            / \
    2   3          2   3
→ True  （完全相同）

p:    1        q:    1
     /              \
    2                2
→ False （結構不同）

套入思維框架：

Base casep 和 q 都是 None → True；其中一個是 None → False
信任遞迴isSameTree(p.left, q.left) 和 isSameTree(p.right, q.right)
組合答案當前節點值相同 AND 左子樹相同 AND 右子樹相同
#100 Same Tree
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # base case：兩個都是 None → 相同
        if not p and not q:
            return True
        # 其中一個是 None，或值不同 → 不相同
        if not p or not q or p.val != q.val:
            return False

        # 信任遞迴，左右子樹都要相同
        return (self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))
⏱ Time: O(n)💾 Space: O(h)

#226 Invert Binary Tree

把每個節點的左右子樹互換，遞迴翻轉整棵樹。

Input / Output
4                4
    / \              / \
   2   7    →      7   2
  / \ / \        / \ / \
 1  3 6  9      9  6 3  1

套入思維框架：

Base casenode 是 None → 直接回傳 None
信任遞迴invertTree(node.left) 回傳翻轉後的左子樹；invertTree(node.right) 同理
組合答案把兩個翻轉後的子樹交叉接回：node.left = 翻轉右，node.right = 翻轉左
#226 Invert Binary Tree
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None

        # 先翻轉左右子樹（信任遞迴）
        left  = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # 交叉接回
        root.left  = right
        root.right = left

        return root
⏱ Time: O(n)💾 Space: O(h)

或者用一行 Python 同時完成：

更簡潔的寫法
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None

        # Python tuple 先求值右邊再賦值（還記得 EP.01 的 swap 嗎？）
        root.left, root.right = (
            self.invertTree(root.right),
            self.invertTree(root.left)
        )
        return root

DFS 的三種遍歷順序

根據「何時處理當前節點」分成三種，只差一行的位置：

Pre / In / Post-order DFS
def dfs(node):
    if not node:
        return

    # ── Preorder（前序）：先處理自己，再遞迴子樹
    process(node.val)
    dfs(node.left)
    dfs(node.right)

    # ── Inorder（中序）：左 → 自己 → 右
    dfs(node.left)
    process(node.val)
    dfs(node.right)

    # ── Postorder（後序）：先遞迴子樹，最後處理自己
    dfs(node.left)
    dfs(node.right)
    process(node.val)

Preorder

root → left → right

Clone tree、Serialize tree

Inorder

left → root → right

BST → Sorted array（BST 的特性）

Postorder

left → right → root

Max Depth、Bottom-up 計算

遞迴寫 Tree 題的關鍵心態：不要試圖在腦中追蹤所有層的狀態。你只需要問：「如果左右子樹都已經給出了正確答案，我怎麼把它們組合起來？」這一步想清楚，剩下的交給 Python 的呼叫棧。

本篇重點整理

🌳Tree DFS = 遞迴，四步：定義、base case、信任遞迴、組合答案
📏Max Depth：max(左深, 右深) + 1，Postorder 思維
🪞Same Tree：值相同 AND 左子樹相同 AND 右子樹相同
🔄Invert：翻轉左右子樹後，交叉接回 root.left / root.right
📋Pre/In/Post-order 只差「何時 process(node)」，放的位置不同

上一篇

EP.08 — Linked List

Pointer 操作與 Dummy Node

下一篇

EP.10 — Tree BFS & BST

Level Order、Validate BST、LCA

LeetCode
Tree
DFS
Recursion
Python
EP.09