题目
- 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
法一、BFS
- 双端队列，前后都可以进出
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
queue = collections.deque()#创建一个双端队列
queue.append(root)#将根节点 root 加入队列中
res = [] #创建一个空列表 res 用于存储最终的结果
while queue: #队列 queue 不为空
size = len(queue)#当前层级的节点数
level = [] #存储当前层级的节点值
for _ in range(size):#循环 size 次
cur = queue.popleft()#从队列的左侧弹出节点 cur
if not cur:#如果当前节点 cur 为空，则继续下一次循环
continue
level.append(cur.val)#将当前节点 cur 的值 cur.val 添加到当前层级的列表 level 中
queue.append(cur.left)#将当前节点 cur 的左子节点 cur.left 加入队列 queue 的右侧。
queue.append(cur.right)#右子节点 cur.right 加入队列 queue 的右侧。
if level:#完成内部循环后，如果 level 列表不为空，则将其添加到结果列表 res 中。
res.append(level)
return res
- 普通队列（单端队列），前出后进
import queue
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
q = queue.Queue()
q.put(root)
res = []
while not q.empty():
size = q.qsize()
level = []
for _ in range(size):
cur = q.get()
if not cur:
continue
level.append(cur.val)
q.put(cur.left)
q.put(cur.right)
if level:
res.append(level)
return res
法二、DFS
- 前序遍历递归实现
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []#创建一个空列表 res 用于存储最终的结果
self.level(root, 0, res)#调用辅助函数 level，并将根节点 root、层级初始值 0 和结果列表 res 作为参数传递给它
return res
def level(self, root, level, res):#函数 level 递归地处理每个层级的节点
if not root: return#当前节点 root 为空直接返回，递归的终止条件
if len(res) == level: res.append([])#如果列表 res 的长度等于当前层级 level，说明当前层级还没有在结果列表中创建对应的子列表，因此使用 res.append([]) 来创建一个空的子列表，用于存储当前层级的节点值。
res[level].append(root.val)#将当前节点 root 的值添加到结果列表 res 的对应层级的子列表中
if root.left: self.level(root.left, level + 1, res)#递归地处理当前节点的左子节点
if root.right: self.level(root.right, level + 1, res)#递归地处理当前节点的右子节点