102. Binary Tree Level Order Traversal

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

層序遍歷：一層一層從上往下走，而且要求輸出是「每一層一個陣列」。

思路

前中後序都是深度優先，用遞迴或棧；層序是唯一的廣度優先，要用佇列。差別在於資料結構的天性：棧會讓你一路往深處鑽，佇列會讓你把同一層先掃完再往下。

這題的難點不在「怎麼走」，而在「怎麼知道一層結束了」。佇列裡同時混著這一層和下一層的節點，光看佇列不為空沒辦法分層。

關鍵技巧只有一行：

for _ in range(len(queue)):

進入迴圈前先把 len(queue) 固定下來 —— 那個數字就是「這一層有幾個節點」。迴圈裡雖然會把下一層的節點 append 進去，但迴圈次數已經定了，所以這一輪只會處理當前這層。這個「先量長度再跑」的手法是所有分層 BFS 的共同骨架，見 BFS / DFS 模板。

想通這件事之後，一整批題目都是同一個骨架換一行：取每層最右邊一個就是 199. Right Side View、取每層最大值就是 515. Find Largest Value in Each Tree Row、奇數層反轉就是 103. Zigzag Level Order。

解題方向

BFS（佇列）

from collections import deque

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:        
        if not root:
            return []
        queue = deque([root])
        res = []
        while queue:
            level = []
            for _ in range(len(queue)):     # 先固定這一層的節點數
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)

        return res

一定要用 deque 不要用 list。 list.pop(0) 是 $O (n)$ （後面所有元素都要往前搬），整體會退化成 $O (n^{2})$ ；deque.popleft() 是 $O (1)$ 。這是 BFS 最常見的效能地雷。

DFS（帶層數的遞迴）

層序的輸出也可以用深度優先做出來 —— 只要把層數當參數傳下去，每個節點就知道自己該放進哪一格：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []

        def helper(node, level):
            if not node:
                return
            if level == len(res):        # 第一次走到這一層，開一個新陣列
                res.append([])
            res[level].append(node.val)

            helper(node.left, level + 1)
            helper(node.right, level + 1)

        helper(root, 0)
        return res

level == len(res) 這個判斷是這版的核心：因為是前序走法，每一層一定是「最左邊那個節點」最先到達，所以第一次遇到某層時 level 剛好等於目前的層數，直接 append 一個空陣列就對位了。

兩版的輸出完全相同，但佇列版比較適合當預設 —— 題目叫 level order，用佇列是最直觀的表達，而且 DFS 版在「求最短路徑」那類的層序題目上不能用（見 111. Minimum Depth，BFS 找到第一個葉節點就能提早結束，DFS 得走完整棵樹）。

補充

四種遍歷一起看：144. 前序、94. 中序、145. 後序、102. 層序。前三種的差別只在「處理自己」那行的位置，層序是另一套骨架，整理見 Tree 遍歷模板。

同一個骨架的變形：103. Zigzag Level Order、199. Right Side View、515. Find Largest Value in Each Tree Row、1302. Deepest Leaves Sum。

複雜度

BFS（佇列）

時間 $O (n)$ — 每個節點進佇列、出佇列各一次
空間 $O (w)$ — w 是樹最寬那一層的節點數；完全二元樹的最後一層約 $n / 2$ ，所以最壞是 $O (n)$

DFS（帶層數）

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

其中 $n$ 是節點數。兩者都不含輸出的 res（那必然是 $O (n)$ ）。

值得注意的是兩種解法的空間取決於不同的維度：BFS 怕「寬」，DFS 怕「深」。完全二元樹對 BFS 最壞（最後一層佔一半節點）、斜樹對 DFS 最壞（遞迴深度 $n$ ）。