思路:
宽搜BFS
队列:每次扩展一层,同时把下一层加入队列
两种方法判断当前层是否结束
方法一:扩展当前层时先计算队列长度
- 每扩展完当前层的节点,就从队列中删掉,删完当前层的元素后
- 查看此时队列剩余节点个数,其实就是下一层有多少个元素
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = [] # 答案是二维数组
if not root: return res
q = deque() # 双向队列
q.append(root)
while len(q) > 0:
leng = len(q) # 记录当前层有多少个节点
level = [] # 每一层的节点
for i in range(leng):
t = q.popleft() # 弹出队头
level.append(t.val)
if t.left: q.append(t.left) # 若当前层的节点有子节点,则加入队列
if t.right: q.append(t.right)
res.append(level) # 加入每一层节点到答案中
return res
方法二:在队列中每一层结尾加上None作为标记,以此区分上下层
- 结束当前层的遍历后,下一层要遍历的点已经在节点队列,所以要在队列尾部加上一个None表示下一层的结束
from collections import deque
class Solution:
def printFromTopToBottom(self, root):
res = []
q = deque([root])
q.append(None) # 初始化队列中有根节点加上None,None表示第一层结束
levelArr = []
while q:
node = q.popleft()
# 新加入
if not node: # 若当前节点为空,证明是当前层结束
if not len(levelArr): # 若层为空,跳出循环
break
res.append(levelArr) # 若层不为空,添加该层数据
levelArr = [] # 将层数据重新清空
q.append(None) # 结束当前层的遍历后,下一层要遍历的点已经在节点队列,所以要在队列尾部加上一个None表示下一层的结束
continue # 继续下一层的遍历
levelArr.append(node.val) # 当前节点非空,加入节点值
if node.left: # 若当前节点有子节点,则加上,作为下一层的节点输入到队列中
q.append(node.left)
if node.right:
q.append(node.right)
return res