本文完整拆解 LeetCode 102 Binary Tree Level Order Traversal 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Binary Tree Level Order Traversal 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
內容目錄
TogglePython
# time complexity: O(n)
# space complexity: O(n)
from typing import List, Optional
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: Optional[TreeNode]) -> List[List[int]]:
result: List[List[int]] = []
def bfs(node: Optional[TreeNode], level: int):
if node is None:
return
if len(result) == level:
result.append([])
result[level].append(node.val)
if node.left:
bfs(node.left, level + 1)
if node.right:
bfs(node.right, level + 1)
bfs(root, 0)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(Solution().levelOrder(root))
Binary Tree Level Order Traversal 解題思路
層序走訪就是 BFS,但要把結果按層分組,關鍵技巧是「在每一輪開始前先記下佇列的長度」——這個長度就是當層的節點數,只處理這麼多個,剩下的都是下一層。這樣不需要為每個節點額外存層數。
Binary Tree Level Order Traversal 演算法步驟
- 若 root 為 null 回傳空陣列;否則把 root 放入佇列。
- 當佇列非空時,先記下 size = 佇列長度,建立當層陣列 level。
- 重複 size 次:取出節點、把值推入 level、把非空的左右子節點推入佇列。
- 把 level 推入結果,繼續下一輪直到佇列為空。
Binary Tree Level Order Traversal 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(n) |
| 空間複雜度 | O(w) |
每個節點恰好進出佇列一次,時間為 O(n)。空間是佇列的最大寬度 w,完全二元樹的最後一層約有 n/2 個節點,所以最壞為 O(n)。
Binary Tree Level Order Traversal 的邊界情況與常見錯誤
- 空樹要回傳空陣列而不是 [[]]。
- 一定要先把 size 存起來再進入內層迴圈,直接用佇列長度當條件會把下一層也吃進來。
- 推入子節點前要檢查非空。
- 若題目要求由下往上(Level Order II),把結果反轉即可。
Binary Tree Level Order Traversal 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| DFS 並用深度當索引分組 | O(n) | O(h) | 程式碼短,但結果順序依賴遞迴 |
| 兩個佇列交替 | O(n) | O(w) | 邏輯等價但多一個容器 |
| 單佇列 + 記錄當層數量 | O(n) | O(w) | 本文採用 |

