---
title: "102. Binary Tree Level Order Traversal"
url: "https://laigary.com/interview/coding/102-binary-tree-level-order-traversal"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Tree", "Breadth-First Search"]
---

# 102. Binary Tree Level Order Traversal

[102\. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

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

## 思路

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

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

關鍵技巧只有一行：

```python
for _ in range(len(queue)):
```

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

想通這件事之後，一整批題目都是同一個骨架換一行：取每層最右邊一個就是 [199. Right Side View](/interview/coding/199-binary-tree-right-side-view)、取每層最大值就是 [515. Find Largest Value in Each Tree Row](/interview/coding/515-find-largest-value-in-each-tree-row)、奇數層反轉就是 [103. Zigzag Level Order](/interview/coding/103-binary-tree-zigzag-level-order-traversal)。

## 解題方向

### BFS（佇列）

```python
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（帶層數的遞迴）

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

```python
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](/interview/coding/111-minimum-depth-of-binary-tree)，BFS 找到第一個葉節點就能提早結束，DFS 得走完整棵樹）。

## 補充

**四種遍歷一起看**：[144. 前序](/interview/coding/144-binary-tree-preorder-traversal)、[94. 中序](/interview/coding/94-binary-tree-inorder-traversal)、[145. 後序](/interview/coding/145-binary-tree-postorder-traversal)、[102. 層序](/interview/coding/102-binary-tree-level-order-traversal)。前三種的差別只在「處理自己」那行的位置，層序是另一套骨架，整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

**同一個骨架的變形**：[103. Zigzag Level Order](/interview/coding/103-binary-tree-zigzag-level-order-traversal)、[199. Right Side View](/interview/coding/199-binary-tree-right-side-view)、[515. Find Largest Value in Each Tree Row](/interview/coding/515-find-largest-value-in-each-tree-row)、[1302. Deepest Leaves Sum](/interview/coding/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$）。