LeetCode 429. N 叉树的层序遍历

约 5 分钟
文章信息 11 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 10-20 字节跳动 美团 快手 腾讯 百度
标签
树 广度优先搜索 层序遍历
目录

题目描述

✅ 429. N 叉树的层序遍历

image-20260329112017033

image-20260329112247131

题意分析

给定一棵 N 叉树，每个节点带一个整数值和一个孩子列表，要求把节点值「按层」收集起来：第一层一个子列表，第二层一个子列表，同层内从左到右。

约束里有两个信号。第一，输出的形状是「二维列表」，说明答案必须能区分「这个节点属于哪一层」，而不只是一串节点值；第二，孩子是一个列表而不是固定的左右两个指针，说明遍历时不能写死两个分支，要对孩子列表整体循环。

边界有三处：根节点为空时应该返回空列表，而不是返回一个包含空层的列表；只有根节点时结果是一个单元素的单层；叶子节点的孩子列表为空，遍历时要能自然跳过而不是抛异常。

解法：队列分层 BFS

核心思路

题目要求按深度分组输出，BFS 的访问顺序天然是先浅后深。队列只负责保证顺序，真正划分层次的是每轮开始时记录的队列长度 size。

循环不变量是：每轮开始时，队列中恰好是当前层的全部节点。固定 size 后只弹出这 size 个节点，并按孩子原有顺序把下一层加入队尾；本轮结束时，队列中便只剩下一层，不变量继续成立。

size 必须在内层循环开始前保存，不能在循环条件里动态读取队列长度。处理当前层时队列还会不断加入孩子，动态长度会把下一层提前混进当前结果。

N 叉树与二叉树的层序模板没有本质差别，只是把固定的左右孩子入队改为遍历 children。

解题步骤

  1. 根节点为空时直接返回空结果。
  2. 将根节点入队。
  3. 每轮先保存 size = queue.size()，创建当前层结果。
  4. 弹出恰好 size 个节点，记录其值，并把所有孩子按顺序入队。
  5. 将当前层加入答案，直到队列为空。

例如根节点 1 的孩子依次是 3、2、4，节点 3 的孩子是 5、6。三轮开始时的队列分别是 [1]、[3,2,4]、[5,6]，所以输出为 [[1],[3,2,4],[5,6]]。

代码实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) {
            return answer;
        }

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>(size);

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node child : node.children) {
                    queue.offer(child);
                }
            }
            answer.add(level);
        }
        return answer;
    }
}

func levelOrder(root *Node) [][]int {
    if root == nil {
        return [][]int{}
    }

    answer := make([][]int, 0)
    queue := []*Node{root}

    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, 0, size)

        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            queue = append(queue, node.Children...)
        }
        answer = append(answer, level)
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$。每个节点恰好入队、出队一次，所有孩子列表的总长度为 $n - 1$。
  • 空间复杂度：$O(w)$，其中 $w$ 是树的最大宽度；返回结果不计入额外空间。

关键点总结

  • 分层 BFS 的关键是每轮开始时冻结当前队列长度。
  • 当前层出队、下一层入队，使“队列只含当前层”的不变量逐轮成立。
  • 孩子必须按原顺序入队，才能保持同层从左到右。
  • 空树返回 []，不是 [[]]。
  • 右视图、每层最大值等题都可复用该模板，只需替换层内聚合逻辑。

易错点总结

  • 内层条件动态使用 queue.size()，会把刚入队的孩子也当成本层节点。
  • 把 level 放在外层循环之外复用，会让各层共享同一个列表。
  • 用栈或把孩子逆序入队，会破坏从左到右的顺序。
  • 根节点为空仍入队，后续访问节点字段会空指针。
  • 只入队固定两个孩子，是把二叉树模板生搬到 N 叉树，可能漏节点。

相似题目

题目 难度 考察点
102. 二叉树的层序遍历 中等 分层 BFS 模板
103. 二叉树的锯齿形层序遍历 中等 层内方向交替
107. 二叉树的层序遍历 II 中等 结果自底向上输出
199. 二叉树的右视图 中等 每层只取最后一个
513. 找树左下角的值 中等 最深层的第一个节点
515. 在每个树行中找最大值 中等 层内求最大值
637. 二叉树的层平均值 简单 层内求平均与溢出
662. 二叉树最大宽度 中等 节点编号计算跨度
958. 二叉树的完全性检验 中等 空节点入队判断完全性
1302. 层数最深叶子节点的和 中等 只保留最后一层求和
LCR 044. 在每个树行中找最大值 中等 层内聚合的变体训练
LCR 045. 找树左下角的值 中等 反向入队简化取值
LCR 046. 二叉树的右视图 中等 BFS 与 DFS 两种写法
剑指 Offer 32 - I. 从上到下打印二叉树 中等 不分层的一维输出
剑指 Offer 32 - II. 从上到下打印二叉树 II 简单 分层输出基础版
剑指 Offer 32 - III. 从上到下打印二叉树 III 中等 双端队列实现之字形
面试题 04.03. 特定深度节点链表 中等 每层就地构造链表