给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
返回其层序遍历结果：
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
解法一
使用字典来保存层次信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = dict()
queue = list()
queue.append((root,0))
while queue:
cur,cur_floor = queue.pop(0)
if cur_floor not in res.keys():
res[cur_floor] = [cur.val]
else:
res[cur_floor].append(cur.val)
if cur.left:
queue.append((cur.left,cur_floor+1))
if cur.right:
queue.append((cur.right,cur_floor+1))
return list(res.values())
|
解法二：官方题解
考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？
我们可以用一种巧妙的方法修改广度优先搜索：
- 首先根元素入队
- 当队列不为空的时候
- 求当前队列的长度$s_i$
- 依次从队列中取$s_i$个元素进行拓展，然后进入下一次迭代。
它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取$s_i$个元素。在上述过程中的第$i$次迭代就得到了二叉树的第$i$层的$s_i$个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def bfs2(self,root:TreeNode):
if not root:
return []
res = []
queue = list()
queue.append(root)
while queue:
temp = []
q_length = len(queue)
for i in range(q_length):
cur = queue.pop(0)
temp.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
res.append(temp)
return res
|
