LeetCode解題之Binary Tree Level Order Traversal
原題
實作樹的廣度優先周遊,每一層上的資料按照從左到右的順序排列。
注意點:
- 無
例子:
輸入:
3
/ \
9 20
/ \
15 7
輸出:
[
[],
[,],
[,]
]
解題思路
将樹每一層的節點存在一個清單中,周遊清單中的元素,如果該節點有左右節點的話,就把它們加入一個臨時清單,這樣當周遊結束時,下一層的節點也按照順序存儲好了,不斷循環直到下一層的清單為空。
AC源碼
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
if not root:
return result
curr_level = [root]
while curr_level:
level_result = []
next_level = []
for temp in curr_level:
level_result.append(temp.val)
if temp.left:
next_level.append(temp.left)
if temp.right:
next_level.append(temp.right)
result.append(level_result)
curr_level = next_level
return result
if __name__ == "__main__":
None
歡迎檢視我的Github (https://github.com/gavinfish/LeetCode-Python) 來獲得相關源碼。