題目出處

102. Binary Tree Level Order Traversal

難度

medium

題目分類

Tree, Breadth-First Search, Binary Tree

個人範例程式碼 – 第二版：2022/4/7

# 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: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []

        queue = [root]
        ans = []
        while(queue):
            tmp_queue = []
            tmp_ans = []
            for ele in queue:
                tmp_ans.append(ele.val)
                if ele.left is not None:
                    tmp_queue.append(ele.left)
                if ele.right is not None:
                    tmp_queue.append(ele.right)
            ans.append(tmp_ans)
            queue = tmp_queue
        else:
            return ans

算法說明

BFS traversal，搭配 Queue 即可完成。
這題沒有發揮 Queue 的 FIFO 特性，但要使用也是可以的。

• 無聊記：Queue = pop(0)，Q 長的很像 0…
• 比較 Stack = pop(-1) 或 pop ()

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

處理 input 為 None 的情況，輸出 []。

Boundary conditions

注意：BFS 結束條件為，「當 Queue 不再有東西的時候」。

個人範例程式碼 – 第一版：2022/3/19

# 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: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        this_level = [root]
        if root:
            while(this_level):
                this_level_val = []
                next_level = []   
                for node in this_level:
                    this_level_val.append(node.val)
                    if node.left:
                        next_level.append(node.left)
                    if node.right:
                        next_level.append(node.right)
                ans.append(this_level_val)
                this_level = next_level

        return ans

算法說明

既然是 level order，我們的思路是使用一層一層的方式下去把答案兜出來。

corner case 特殊情況處理

當樹為空 [] 或 為只有 root [1] 時，需要注意。

Boundary conditions/ Edge conditions 邊際情況處理

原本的做法我是到最後一層才做檢查「if root」，
不過如果是採取這樣的作法，會多一層只有「None 的 layer」，
我們需要特別留意儲存的最後一層。

Reference

• 二叉树的层次遍历 · Binary Tree Level Order Traversal
• ?? Python | BFS Queue – 公瑾™ (102)