題目
思路
- 一次一層很直覺想到廣先搜尋 (BFS)，所以用 iterative 的做法來解
- 一次迴圈處理一層，並把下一層節點放入 stack 繼續在下次迴圈處理
- stack 也是 list of list, 裡面的每個 list 都是一層節點
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
stack, values = [[root]], []
while stack:
level_vals = []
level_nodes = []
nodes = stack.pop()
for node in nodes:
level_vals.append(node.val)
if node.left:
level_nodes.append(node.left)
if node.right:
level_nodes.append(node.right)
if level_nodes:
stack.append(level_nodes)
values.append(level_vals)
return values
|
但假如用遞迴的話怎麼解？
Recursive case: 把當下這個節點的 value 放到對應 level index 的 list 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def put_value(node, level_ind, res):
if not node:
return
try:
level = res[level_ind]
except IndexError:
level = []
res.append(level)
level.append(node.val)
put_value(node.left, level_ind + 1, res)
put_value(node.right, level_ind + 1, res)
if not root:
return []
res = []
put_value(root, 0, res)
return res
|
