LeetCode 刷題日記
EP.10

Tree BFS & BST
層序遍歷、驗證 BST、找共同祖先

#102 Level Order · #98 Validate BST · #235 LCA

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

EP.09 用 DFS 打通了遞迴的思維，這篇接著講三個不同的 Tree 主題：BFS 層序遍歷（用 Queue 而非遞迴）、BST 的驗證（Binary Search Tree 的隱含約束），以及 LCA 最近公共祖先（Tree 中最優雅的遞迴之一）。

DFS vs BFS：兩種遍歷方式

DFS（深度優先）

一路往深處走，到底再回頭。用遞迴或 Stack 實作。

訪問順序：1→2→4→5→3→6→7

BFS（廣度優先）

一層一層向外擴，用 Queue（deque） 實作。

訪問順序：1→2→3→4→5→6→7

「按層」這個特性讓 BFS 天然適合 Level Order Traversal 和「找最短路徑」類的問題。

#102 Binary Tree Level Order Traversal

按照層次，從上到下、從左到右輸出每一層的節點值。

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

Output: [[3], [9, 20], [15, 7]]

BFS 的標準實作用 collections.deque。關鍵是：每次進入 while loop 時，queue 裡剛好放著「當前層的所有節點」。

#102 Level Order Traversal — BFS
from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])   # 用 deque 當 Queue

        while queue:
            level_size = len(queue)   # 當前層的節點數
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()          # 從左邊取出（FIFO）
                current_level.append(node.val)

                if node.left:
                    queue.append(node.left)     # 下一層的節點放到右邊
                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result
⏱ Time: O(n)💾 Space: O(n) 最寬的那一層最多 n/2 個節點

為什麼用 deque 而不是 list？

list.pop(0) 是 O(n)（要搬移所有元素），deque.popleft() 是 O(1)。Queue 的 dequeue 操作一定要用 deque。

逐步追蹤：

初始queue=[3]result=[]
第1層queue=[9,20]result=[[3]]
第2層queue=[15,7]result=[[3],[9,20]]
第3層queue=[]result=[[3],[9,20],[15,7]] ✅

#98 Validate BST：理解 BST 的真正約束

BST（Binary Search Tree）的定義：左子樹的所有節點值 < 當前節點值 < 右子樹的所有節點值。

注意：是所有節點，不只是直接的左右子節點。

看起來合法，其實不合法
5
    / \
   1   4     ← 4 < 5 ✓（看起來沒問題）
      / \
     3   6   ← 3 < 5 但是！3 在 5 的右子樹，必須 > 5 ✗

→ False（3 違反了 BST 的全局約束）

錯誤解法：只比較 node.left.val < node.val < node.right.val，這樣會漏掉全局約束。

正確做法：傳入合法值範圍（min_val, max_val），每往下走一層就縮緊範圍。

#98 Validate BST — 傳遞範圍約束
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def validate(node, min_val, max_val):
            if not node:
                return True

            # 當前節點必須在 (min_val, max_val) 範圍內
            if not (min_val < node.val < max_val):
                return False

            # 往左走：上界縮緊為當前節點值
            # 往右走：下界縮緊為當前節點值
            return (validate(node.left,  min_val,  node.val) and
                    validate(node.right, node.val, max_val))

        return validate(root, float('-inf'), float('inf'))
⏱ Time: O(n)💾 Space: O(h)

上面那棵有問題的樹，用範圍追蹤：

validate(5, -∞, +∞) → 5 在範圍內 ✓
validate(1, -∞, 5) → 1 在範圍內 ✓
validate(4, 5, +∞) → 4 < 5，不在範圍 (5, +∞) 內 ✗ → False

#235 Lowest Common Ancestor（LCA）

給 BST 中的兩個節點 p 和 q，找它們的最近公共祖先（LCA）——兩個節點的共同祖先中，最靠近它們的那個。

Input / Output
6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

LCA(2, 8) = 6   ← 6 是最近的共同祖先
LCA(2, 4) = 2   ← 2 本身就是 4 的祖先，所以答案是 2

利用 BST 的性質：

→p 和 q 都比當前節點小 → LCA 在左子樹
→p 和 q 都比當前節點大 → LCA 在右子樹
→一個比當前節點小、一個比當前節點大（或其中一個就是當前節點）→ 當前節點就是 LCA
#235 LCA of BST
class Solution:
    def lowestCommonAncestor(self, root: TreeNode,
                              p: TreeNode, q: TreeNode) -> TreeNode:
        # p 和 q 都在左邊
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        # p 和 q 都在右邊
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        # 分叉了，或其中一個就是 root → root 就是 LCA
        return root
⏱ Time: O(h) h=樹高💾 Space: O(h)
⚠️ 這題是 BST 的 LCA，利用了 BST 的大小關係。如果是普通 Binary Tree（沒有大小關係），需要用不同的解法（Post-order DFS，同時從兩個子樹找）。

何時用 DFS，何時用 BFS？

需要「按層」處理

Level Order、找最短路徑

BFS

需要「從底部往上」累積結果

Max Depth、Diameter

DFS (Postorder)

需要「從頂部往下」傳遞資訊

Validate BST（傳遞範圍）

DFS (Preorder)

找路徑、找是否存在

Path Sum、Same Tree

DFS

樹非常深（接近線性），怕 stack overflow

退化成 Linked List 的樹

BFS（迭代）

BST 題目的核心是利用大小關係「剪枝」——每次可以丟掉一半，把 O(n) 降到 O(h)。這和 Binary Search 的精神完全一樣：每步都能保證目標「不在那裡」，所以可以安全丟掉。

本篇重點整理

🔁BFS = Queue（deque），popleft() 取出，append() 放入，按層處理
⚠️list.pop(0) 是 O(n)，Queue 操作一定要用 deque.popleft()
🌲Validate BST：傳遞 (min, max) 範圍，每層縮緊，而非只比左右子節點
🔗LCA on BST：p、q 分佈在兩側就是分叉點，純粹利用 BST 大小關係
🧭按層 → BFS；底部累積 → Post-order DFS；頂部傳遞 → Pre-order DFS

上一篇

EP.09 — Tree & DFS

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

下一篇

EP.11 — Dynamic Programming

即將推出

LeetCode
Tree
BFS
BST
Python
EP.10