題目出處
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」，
我們需要特別留意儲存的最後一層。