[LeetCode] #102. Binary Tree Level Order Traversal
題目
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).
直覺解
構想：
把第 n 層的節點由左而右存到 list 裡。要計算 n+1 層有哪些節點時，就用 for 迴圈迭代第 n 層的節點，每一圈都把該節點的左節點和右節點存起來。作法跟我在 #236. Lowest Common Ancestor of a Binary Tree 時把 Tree 轉成 array 的那一步類似。
沒有用 level 之類的變數紀錄現在是 tree 的哪一層，所以在計算 n+1 層有哪些節點時，還沒算完整層之前，是先把結果暫時儲存在別的 list，算完後再一口氣把結果 append 到 ans 裡
用 flag 判斷是否該結束 while 迴圈
python 3 實作：
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
ans = [[root.val]]
uncheckNode = [root]
isDone = False
while not isDone:
tempAns = []
tempUncheckNode = []
isDone = True
for node in uncheckNode:
if not node:
continue
if node.left:
tempAns.append(node.left.val)
tempUncheckNode.append(node.left)
isDone = False
if node.right:
tempAns.append(node.right.val)
tempUncheckNode.append(node.right)
isDone = False
if not isDone:
ans.append(tempAns)
uncheckNode = tempUncheckNode
return ans
效能：
Runtime: 32 ms, faster than 84.13% of Python3 online submissions for Binary Tree Level Order Traversal.
Memory Usage: 14.6, less than 44.09% of Python3 online submissions for Binary Tree Level Order Traversal.
參考別人的解一
來源：Python, DFS
構想：
用 recursion。用 levele 變數紀錄現在是哪一層
自己的 python 3 實作：
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = []
level = 0
def traversal(root, level):
if not root:
return
if len(ans) == level:
ans.append([])
ans[level].append(root.val)
traversal(root.left, level + 1)
traversal(root.right, level + 1)
traversal(root, level)
return ans
效能：
Runtime: 36 ms, faster than 61.43% of Python3 online submissions for Binary Tree Level Order Traversal.
Memory Usage: 15.4 MB, less than 7.58% of Python3 online submissions for Binary Tree Level Order Traversal.
參考別人的解二
來源：Easy Python Queue Solution || Beats 99%
構想：
用 queue，在 queue 裡面用 None 分隔不同層的節點。用 levele 變數紀錄現在是哪一層。
自己的 python 3 實作：
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = []
if not root:
return ans
queue = [root, None]
level = 0
while queue:
node = queue.pop(0)
if node:
if len(ans) == level:
ans.append([])
ans[level].append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
elif len(queue):
level += 1
queue.append(None)
return ans
效能：
Runtime: 36 ms, faster than 61.43% of Python3 online submissions for Binary Tree Level Order Traversal.
Memory Usage: 14.7 MB, less than 44.09% of Python3 online submissions for Binary Tree Level Order Traversal.
Comments
Post a Comment