題目出處
107. Binary Tree Level Order Traversal II
難度
medium
題目分類
Tree, Breadth-First Search, Binary Tree
個人範例程式碼
# 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
ans = []
queue = [root]
while(queue):
tmp_ans = []
tmp_queue = []
for node in queue:
tmp_ans.append(node.val)
if node.left is not None:
tmp_queue.append(node.left)
if node.right is not None:
tmp_queue.append(node.right)
ans.append(tmp_ans)
queue = tmp_queue
else:
return ans[::-1]
算法說明
這題有幾乎相同的類似題，可參考：
https://wongwongnotes-github-io.pages.dev/python/leetcode-python-102/
BFS traversal，搭配 Queue 即可完成。
這題沒有發揮 Queue 的 FIFO 特性，但要使用也是可以的。
- 無聊記：Queue = pop(0)，Q 長的很像 0…
- 比較 Stack = pop(-1) 或 pop ()
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為 None 的情況，輸出 []。
Boundary conditions
注意：BFS 結束條件為，「當 Queue 不再有東西的時候」。