LeetCode 102. 二叉树的层序遍历

约 5 分钟
文章信息 34 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 200-500 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 小米 百度 网易 小红书 快手 滴滴 携程 B站 虾皮 OPPO 商汤 旷视 深信服 陌陌 猿辅导 作业帮
标签
树 广度优先搜索 二叉树

题目描述

✅ 102. 二叉树的层序遍历

:::fold 历史考题

考察公司：美团

:::

image-20260928184109280

image-20260928184109281

题意分析

从根节点开始，按从上到下的层次遍历二叉树，同一层按从左到右的顺序访问，返回各层的节点值。

返回结果需要按层分组：每一层对应一个列表，不能把所有节点值放进同一个列表。空树返回空结果，缺失的孩子不需要用空值占位。

解法：BFS 队列按层遍历

核心思路

[!blue]

使用先进先出的队列保存待访问节点。先将根节点入队，每取出一个节点，就按先左后右的顺序把它的非空孩子放到队尾。当前层尚未访问的节点排在这些孩子前面，因此会先访问完当前层，再访问下一层；父节点从左到右出队，也保证孩子按从左到右的顺序入队。

队列能保证访问顺序，但还需要明确每层在哪里结束。每轮开始时，队列中恰好保存当前层的全部节点，先将它的长度保存为 levelSize，本轮只取出这么多个节点，并把它们的值放入一个新的列表。

处理期间入队的孩子属于下一层，不改变已经记录的 levelSize。当前层处理完后，把这一层的列表加入结果；此时队列中只剩下一层的节点，重复相同过程，直到队列为空。

解题步骤

  1. 空树直接返回空结果，否则将根节点入队。
  2. 每轮开始先记录队列长度 levelSize，并创建当前层的结果列表。
  3. 固定出队 levelSize 个节点，收集节点值，并按先左后右的顺序将非空孩子入队。
  4. 将当前层列表加入结果，继续处理下一层，直到队列为空。

代码实现

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            // 固定本层数量，新加入的孩子留在下一层处理。
            int levelSize = queue.size();
            // 每层创建独立容器，避免后续修改覆盖旧层。
            List<Integer> level = new ArrayList<>(levelSize);

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(level);
        }

        return result;
    }
}

func levelOrder(root *TreeNode) [][]int {
    result := make([][]int, 0)
    if root == nil {
        return result
    }

    queue := []*TreeNode{
        root,
    }
    for len(queue) > 0 {
        // 固定本层数量，新加入的孩子留在下一层处理。
        levelSize := len(queue)
        // 每层创建独立容器，这里预留容量但长度从零开始。
        level := make([]int, 0, levelSize)

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, level)
    }
    return result
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点入队、出队各一次。
  • 空间复杂度：$O(w)$，w 为二叉树的最大宽度；不计返回结果。

关键点总结

[!green]

  • 外层循环每次处理一整层，队列负责维持从左到右的顺序。
  • 必须在处理当前层前固定 levelSize，避免把下一层提前消费。
  • 孩子按先左后右入队，空节点不入队。

易错点总结

[!yellow]

  • 在循环条件里动态读取队列长度，会因孩子不断入队而破坏分层。
  • 空树未提前返回，可能把空节点入队并触发空指针。
  • 复用同一个层列表，会让多层结果引用同一份数据。
  • Go 中 make([]int, levelSize) 已创建了指定长度，再 append 会产生多余零值；这里只预分配容量。

相似题目

题目 难度 关联与区别
103. 二叉树的锯齿形层序遍历 中等 分层逻辑相同，原题每隔一层反转输出顺序，本题一直从左到右。
107. 二叉树的层序遍历 II 中等 同样先按层收集，原题最终要求从最深层到根层输出。
199. 二叉树的右视图 中等 按层遍历并在同一层内聚合；本题保留每层全部节点，该题每层只取最右节点。
515. 在每个树行中找最大值 中等 按层遍历并在同一层内聚合；本题保留每层全部节点，该题每层只保留最大节点值。
637. 二叉树的层平均值 简单 按层遍历并在同一层内聚合；本题保留每层全部节点，该题累计每层总和及节点数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/87203213
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！