- 标签:树、广度优先搜索
- 难度:中等
给定一个二叉树,请你返回其按「层序遍历」得到的节点值。
注意:返回结果为二维数组,每一层都要存为数组返回。
比如:
3
/ \
9 20
/ \
15 7
返回结果为:
[
[3],
[9,20],
[15,7]
]
广度优先搜索,需要增加一些变化。普通广度优先搜索只取一个元素,变化后的广度优先搜索每次取出第 i
层上所有元素。
具体步骤如下:
- 根节点入队。
- 当队列不为空时,求出当前队列长度
$s_i$ 。- 依次从队列中取出这
$s_i$ 个元素,将其左右子节点入队,遍历完之后将这层节点数组加入答案数组中,然后继续迭代。
- 依次从队列中取出这
- 当队列为空时,结束。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = [root]
order = []
while queue:
level = []
size = len(queue)
for _ in range(size):
curr = queue.pop(0)
level.append(curr.val)
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
if level:
order.append(level)
return order