102. 二叉树的层序遍历 Medium

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

示例 1:
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2:
输入：root = [1]
输出：[[1]]

示例 3:
输入：root = []
输出：[]

解题思路

输入： 一个二叉树的根节点 root。

输出： 返回节点值的 层序遍历。

本题属于遍历二叉树问题，典型的 广度优先搜索（BFS），也称为 层序遍历。

• 我们使用一个队列（Queue），按“从左到右、从上到下”的顺序逐层遍历节点：
• 每次从队列中取出当前层的所有节点
• 依次访问这些节点，记录它们的值
• 将它们的左子节点和右子节点加入队列
• 重复此过程，直到队列为空

代码实现

python

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 空树处理
        if not root:
            return []

        res = []  # 用于存储每一层的遍历结果
        queue = [root]  # 使用队列作为 BFS 队列，初始放入根节点

        while queue:
            level = []  # 存放当前层的节点值
            level_size = len(queue)  # 当前层的节点个数

            for _ in range(level_size):
                node = queue.pop(0)  # 弹出队头节点（当前层）
                level.append(node.val)  # 记录节点的值

                # 将下一层节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            res.append(level)  # 当前层遍历完，加入结果列表

        return res

javascript

const levelOrder = function(root) {
    // 空树处理
    if (!root) return [];

    // 用于存储每一层的遍历结果
    const res = [];
    // 使用队列作为 BFS 队列，初始放入根节点
    const queue = [root];

    while (queue.length) {
        // 存放当前层的节点值
        const levels = [];
        // 当前层的节点个数
        const size = queue.length;

        for (let i = 0; i < size; i++) {
            // 弹出队头节点（当前层）
            const node = queue.shift();
            // 记录节点的值
            levels.push(node.val);

            // 将下一层节点加入队列
            if (node.left) {
                queue.push(node.left);
            }
            // 注意这里不能用 else if 因为这里是独立的逻辑
            if (node.right) {
                queue.push(node.right);
            }
        }

        // 当前层遍历完，加入结果列表
        res.push(levels);
    }

    return res;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

102 国际版

102 中文版