Binary Tree Level Order Traversal 解題教學:3 種解法完整比較|LeetCode 102 Best Practice

Binary Tree Level Order Traversal 解題教學示意圖|LeetCode 102

本文完整拆解 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
				
					# 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 演算法步驟

  1. 若 root 為 null 回傳空陣列;否則把 root 放入佇列。
  2. 當佇列非空時,先記下 size = 佇列長度,建立當層陣列 level。
  3. 重複 size 次:取出節點、把值推入 level、把非空的左右子節點推入佇列。
  4. 把 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)本文採用