题目描述

102. 二叉树的层序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思路

使用队列，先进先出

怎么知道每层队列循环多少次？

        在每次循环开始时候获取队列的长度

当队列为空时就退出循环

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 使用双端队列
        # 如果根节点为空，返回空数组
        if root is None:
            return []
        # 数组存储结果
        res = []
        # 队列计算当前层的节点
        q = deque([root])
        # 当队列不为空时
        while q:
            # 存储当前层的结果
            vals = []
            # 当前 队列长度即为当前层循环的次数
            for _ in range(len(q)):
                node = q.popleft()
                vals.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            res.append(vals)
        return res

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)。满二叉树最后一层有 n/2 个节点

注意事项

vals的作用：

• 有 vals 时，结果是 [[3], [9,20], [15,7]]（按层分组）

• 没有 vals 时，会得到 [3,9,20,15,7]（扁平列表，丢失层信息）

注意本题的要求是需要按层分组