102. 二叉树的层序遍历（中）

• 题目
• 法一、BFS
• 法二、DFS

题目

• 给你二叉树的根节点 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)#递归地处理当前节点的右子节点