二元樹與 BST 實戰：5 題從讀題推導到最優解（LC 104/102/236/98/230）

樹的題目看起來千變萬化，但拆到底只有兩條主線：① 選對遍歷方式（DFS 還是 BFS），② 是不是 BST、能不能用「左 < 根 < 右」的性質。把這兩件事想清楚，大部分樹題就只是套模板。

這篇用 5 題串起這兩條主線，延續一貫的完整推導流程：

📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼

• DFS 遞迴求深度（104）→ BFS 分層走訪（102）→ DFS 靠子樹回傳值找 LCA（236）→ DFS 帶上下界驗證 BST（98）→ BST 中序的有序性質找第 k 小（230）

🌲 前置：以下都用標準節點定義。Python：node.val / node.left / node.right；C++：TreeNode { int val; TreeNode *left, *right; }。

① LC 104 — Maximum Depth of Binary Tree

📋 題目：給定一棵二元樹的根節點，回傳其最大深度（從根到最遠葉節點的節點數）。

範例：root = [3,9,20,null,null,15,7] → 3

🌐 EN — Given the root of a binary tree, return its maximum depth (the number of nodes along the longest path from the root down to the farthest leaf). Example: root = [3,9,20,null,null,15,7] → 3

🧭 從讀題到解法

1. 拆解：一棵樹的深度 = 1（根自己）+ 左右子樹中較深的那個。這是天然的遞迴定義。
2. 直覺解：直接遞迴，base case 是空節點回 0。
3. 關鍵洞察：這就是最乾淨的 DFS（後序）——先算出左右子樹深度，再合併。
4. 最優解：三行遞迴。

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

• 複雜度：時間 O(n)（每個節點走一次），空間 O(h)（遞迴堆疊，h 為樹高；最壞 O(n)）。
• 坑：深度算的是節點數不是邊數；空樹回 0。若樹極度傾斜（鏈狀），遞迴深度 O(n) 可能 stack overflow，可改 BFS。

② LC 102 — Binary Tree Level Order Traversal

📋 題目：給定二元樹根節點，回傳逐層由左到右的節點值（每一層一個陣列）。

範例：root = [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

🌐 EN — Given the root of a binary tree, return the level-order traversal of its node values (left to right, one array per level). Example: root = [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

🧭 從讀題到解法

1. 拆解：要「逐層」輸出——這是 DFS 不擅長的，DFS 會往深處鑽。要的是廣度優先。
2. 暴力解：先求高度，再對每一層各掃一次，O(n·h)，浪費。
3. 關鍵洞察（BFS）：用一個佇列，每一輪先記住當前佇列大小 sz，那 sz 個就是同一層；把它們全部彈出、收集，並把它們的子節點推入佇列當作下一層。
4. 最優解：迴圈內用 len(queue) 切分層級。

from collections import deque

def levelOrder(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):       # freeze this level's size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();            // freeze this level's size
        vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

• 複雜度：時間 O(n)，空間 O(n)（佇列最寬一層）。
• 坑：一定要先凍結 sz = len(q) 再迴圈——迴圈中會往佇列加下一層節點，若用動態長度判斷會把不同層混在一起。這是分層 BFS 的命門。

③ LC 236 — Lowest Common Ancestor of a Binary Tree

📋 題目：給定二元樹與兩個節點 p、q，回傳它們的最低共同祖先（LCA）。注意是普通二元樹，不是 BST。

範例：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3；p = 5, q = 4 → 5（一個節點可以是自己的祖先）

🌐 EN — Given a binary tree and two nodes p, q, return their lowest common ancestor (LCA). Note it's a plain binary tree, not a BST. Example: p = 5, q = 1 → 3; p = 5, q = 4 → 5 (a node can be its own ancestor)

🧭 從讀題到解法

1. 拆解：LCA = 「同時能在其左右子樹（或自己）裡找到 p 和 q 的最深節點」。
2. 暴力解：分別求 p、q 到根的路徑，再找最後一個公共節點，O(n) 但要存兩條路徑。
3. 關鍵洞察（後序 + 子樹回傳值）：對每個節點問「我的子樹裡有沒有 p 或 q？」。遞迴回傳：找到就回那個節點、沒找到回 null。若某節點的左右子樹各回傳一個非 null（一邊有 p、一邊有 q），那它就是 LCA；若只有一邊有，就把那邊往上傳。
4. 最優解：一次後序 DFS，不需額外存路徑。

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lowestCommonAncestor(root.left,  p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:          # p and q split across both sides → here is LCA
        return root
    return left or right        # both on one side → bubble it up

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left  = lowestCommonAncestor(root->left,  p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;     // split → LCA
    return left ? left : right;         // one side → bubble up
}

• 複雜度：時間 O(n)，空間 O(h)。
• 坑：① base case 包含 root == p or root == q——因為節點可以是自己的祖先；② 這題不能用 BST 的值比較（它是普通二元樹），要靠子樹回傳值。對照下一題 235（BST 版 LCA）可直接比大小。

④ LC 98 — Validate Binary Search Tree

📋 題目：給定二元樹，判斷它是否為合法 BST：每個節點的左子樹所有值 < 該節點 < 右子樹所有值。

範例：root = [2,1,3] → true；root = [5,1,4,null,null,3,6] → false（4 在 5 的右子樹卻 < 5）

🌐 EN — Given a binary tree, determine if it is a valid BST: every node's left subtree has values all less than the node, and the right subtree all greater. Example: root = [2,1,3] → true; root = [5,1,4,null,null,3,6] → false (4 is in 5's right subtree but < 5)

🧭 從讀題到解法

1. 拆解：BST 的條件是整棵子樹的範圍，不只是直接子節點。
2. 錯誤的直覺：只檢查 left.val < node.val < right.val。反例：[5,1,4,null,null,3,6] 裡 4 是 5 的右孫，局部看 3<4<6 沒問題，但 4 < 5 違反全域 BST——局部比較會漏掉。
3. 關鍵洞察（帶上下界遞迴）：往下遞迴時，把「允許的開區間 (low, high)」一路收緊：走左子樹時上界變成 node.val，走右子樹時下界變成 node.val。每個節點檢查是否落在自己的區間內。
4. 最優解：DFS 帶 (low, high)，初始 (-∞, +∞)。

def isValidBST(root):
    def valid(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):     # must fit the open interval
            return False
        return (valid(node.left,  low, node.val) and
                valid(node.right, node.val, high))
    return valid(root, float('-inf'), float('inf'))

bool valid(TreeNode* node, long low, long high) {
    if (!node) return true;
    if (!((long)node->val > low && (long)node->val < high)) return false;
    return valid(node->left, low, node->val) &&
           valid(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) {
    return valid(root, LONG_MIN, LONG_MAX);
}

• 複雜度：時間 O(n)，空間 O(h)。
• 坑：① 不能只比直接子節點，要傳遞上下界；② 節點值可能等於 INT_MIN/INT_MAX，C++ 用 long 當界避免溢位、Python 用 ±inf；③ BST 不允許重複值，要用嚴格不等號。替代解：中序走訪應嚴格遞增，邊走邊比前一個值（見下一題的中序思路）。

⑤ LC 230 — Kth Smallest Element in a BST

📋 題目：給定 BST 與整數 k，回傳其中第 k 小的元素（1-indexed）。

範例：root = [3,1,4,null,2], k = 1 → 1；root = [5,3,6,2,4,null,null,1], k = 3 → 3

🌐 EN — Given a BST and an integer k, return the kth smallest element (1-indexed). Example: root = [3,1,4,null,2], k = 1 → 1; root = [5,3,6,2,4,null,null,1], k = 3 → 3

🧭 從讀題到解法

1. 拆解：要「第 k 小」——若能拿到由小到大排序的序列，第 k 個就是答案。
2. 暴力解：把所有值取出排序，O(n log n)，但沒用上 BST。
3. 關鍵洞察（BST 中序 = 升序）：BST 的中序走訪（左 → 根 → 右）剛好是由小到大。所以只要中序走訪，數到第 k 個就回傳，根本不用走完整棵樹。
4. 最優解：用迭代中序（顯式堆疊）邊走邊計數，數到 k 立即回傳。

def kthSmallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                  # go as left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()           # visit in ascending order
        k -= 1
        if k == 0:
            return node.val
        node = node.right            # then the right subtree

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (!st.empty() || node) {
        while (node) { st.push(node); node = node->left; }   // leftmost
        node = st.top(); st.pop();                            // visit
        if (--k == 0) return node->val;
        node = node->right;                                   // go right
    }
    return -1;
}

• 複雜度：時間 O(h + k)（只走到第 k 個），空間 O(h)。
• 坑：① 關鍵是「中序 = 升序」，這是 BST 專屬性質；② 用迭代中序能提早結束（數到 k 就停），比「全部收集再取第 k」省；③ 追問：若 BST 會頻繁增刪、又常查第 k 小，可在每個節點維護「左子樹節點數」，把單次查詢降到 O(h)。

一張表記住全部

面試辨識口訣

• 看到「深度 / 高度 / 路徑和 / 翻轉」→ DFS 遞迴，想「左右子樹各回傳什麼、怎麼合併」。
• 看到「逐層 / 每一層 / 最右節點 / 之字形」→ BFS，記得凍結 sz 分層。
• 看到「LCA / 兩節點關係」→ 後序 DFS 用子樹回傳值；若是 BST 可直接比大小（235）。
• 看到「驗證 BST」→ 帶上下界遞迴，或中序檢查嚴格遞增。
• 看到「BST + 第 k 小 / 排序 / 範圍查詢」→ 中序走訪（升序），能提早結束。

樹題的精髓就兩句：「這題該用 DFS 還是 BFS？」以及「它是 BST 嗎？能不能用左<根<右？」。先答這兩題，程式碼幾乎是自動寫出來的。