1. 题目定位与核心思路拆解
这道题是我刷力扣时除了二叉树之外，第一个觉得“有意思”的层序类题目。力扣429的定位很简单，就是让你实现N叉树的层序遍历，输出的不是一维数组，而是二维数组，每一层的结果单独放一个子数组里。
我第一次刷的时候，第一反应是“这不就是二叉树的层序遍历换了个壳吗？”可真上手写了代码才发现，坑不多，但坑都在看不见的地方。比如：孩子节点不是固定的 left 和 right，而是放在一个 List 里；再比如，如果层序遍历的 BFS 模板没有吃透，直接把二叉树代码改过来，很容易出现“本应是同一层的节点被切成了两个数组”这种其实很隐蔽的结果错误。
先说题目本身：N叉树的定义是每个节点最多有 N 个孩子，而力扣默认的输入是层序序列化的形式，但刷题时我们按题目给出的 Node 结构来操作就行，不需要自己构建树。核心要求非常明确：返回一个 List<List >，外层代表层号，内层是该层的所有节点值，顺序是从左到右。
那这道题最大的价值在什么地方呢？就是练 BFS 的分层处理能力。层序遍历本身是广度优先搜索的经典场景，而“按层输出”这个附加条件，恰恰就是算法面试笔试里极高频的考察点——类似“每层平均值”“每层最大值”“锯齿形遍历”都是在它的基础上变种出来的。你把这一题的模板吃透了，二叉树、N叉树、甚至图的按层遍历，基本就是换皮不换骨。
相对适合谁来刷呢？我觉得是三类人：一是刚学完二叉树、准备系统入门图论的初学者；二是准备笔试面试、需要熟练秒杀层序类题目的应届生；三是自己写业务代码很少接触树结构、但想补算法基本功的转行工程师。这道题难度属于中等偏下，但它考察的是对队列和逐层边界的理解，容错率低，非常能看出编码功底。
2. BFS 的分层逻辑与原理解密
2.1 为什么队列天生适合层序遍历
层序遍历的本质，是按照“离根节点越近，越先被访问”的顺序输出节点。要实现这个顺序，最直观的数据结构就是队列（Queue），先进先出。
我打个比方你就懂了：层序遍历就像一队人排队进电梯。根节点先进电梯，出来之前，把它的孩子们拉到队尾排队；然后第二个节点再进电梯，出来时又把它的孩子们排到队尾。整个过程里，谁先进去谁先出来，你每次读到的节点顺序，一定是按层扩散开的。
这里有个容易懵的点：为什么用栈不行？栈是先进后出，顺序正好反了，会变成深度优先的形态。所以层序遍历的第一原则，就是选队列，别整花活。力扣上有些人用递归做层序，那是用递归强行模拟“层”的概念，我后面会讲它的实现逻辑，但核心手段仍然是“层号对齐”。
2.2 层序输出的核心难点：如何确定“这一层”的边界
二叉树的层序遍历，很多题解上来就写 while + for 循环，for 循环的次数是当前队列长度，但很多初学者不理解这个 for 为什么这么写，以及为什么不能用 while (!queue.isEmpty()) 一路 poll 下去。
关键就在“边界”二字。BFS 在没有分层标记的情况下，它只知道“按顺序访问”，并不知道当前访问到的是第几层。如果你只在 while 里做一次 poll，那这个循环会一直走到整棵树被访问完，输出的结果必然是一维数组，因为它根本不知道“该换行了”。
那如何让它知道该换行了？两个思路：
- 分层标记法：在队列里塞一个特殊值（比如 null）作为行尾标识，遇到 null 就知道这层结束了；
- 队列快照法：每次进入下一层之前，先记录当前队列的 size，这个 size 就是当前层的节点数量，然后只从这个数量里 poll，poll 完了这层就结束了。
第二个思路是现在的主流做法，也是力扣官方题解采用的方式。它的原理很好理解：队列里永远只保存“当前层节点的所有孩子”，也就是“下一层的完整节点集合”。你在处理当前层之前，队列里有多少个节点，就代表当前层有多少个节点，这个数量是“快照”，for 循环就是按这个快照把本层节点全部消费完。
我刷题时的一个体会是：这个 for + size 快照的组合，看起来简单，但它是所有层序类题目的万能钥匙。你把 for 内部换成求 max、求 sum、处理旋转逻辑，换一换代码块，就变成了不同的题目。所以这个模板值得专门背下来。
2.3 N叉树和二叉树的差异边界
二叉树和 N叉树最大的不同，就在于孩子节点这个字段。二叉树的节点定义是 left 和 right，N叉树是一个 List children。这导致遍历孩子时，你需要一个 for 或者增强 for 循环，把当前节点的所有子节点都加入队列。
这也是 N叉树唯一一个比二叉树多写代码的地方。其他逻辑，包括队列快照、层数组、结果收集，完全一模一样。
我在第一次改代码的时候犯过一个低级错误：直接把二叉树的 left 和 right 入队，结果编译直接报错，因为 N叉树的节点定义里压根没有这两个属性。这个错犯得很丢人，但也提醒我，刷题前最好先看清题目给的 Node 定义，别凭惯性直接写。
3. 核心解法：队列迭代实现逐层输出
3.1 完整可通过的 Java 实现
我平时刷力扣主力语言是 Java，先把可以直接提交的完整代码贴出来，再逐行讲它在干什么。
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> levelList = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { Node node = queue.poll(); levelList.add(node.val); if (node.children != null) { for (Node child : node.children) { queue.offer(child); } } } result.add(levelList); } return result; } }这个代码拿去过力扣是完全没问题的，执行时间在绝大多数测试用例下都是 0ms 或接近 0ms，内存消耗属于正常水平。下面我把它拆开，逐个说每一段的意义。
3.2 初始化边界：为什么 root 为空要单独处理
第一处容易被忽略的代码是：
if (root == null) { return result; }这道题如果把 root 为空的情况直接丢进 while 循环，其实也不会报错，队列为空，整个 while 直接不执行，返回的也是空二维数组。所以我见过不少人把这段判断省略掉，也能通过。但我还是建议写上，原因有两个：
一是代码意图更明确。读代码的人第一眼就知道，树是空的时候你期望的返回值是空数组，而不是 null，更不是报错。
二是防止后续在循环里对 root 做操作时疏忽。如果你在循环外先对 root 做了什么赋值或者判断，root 为空的隐患就会放大。养成“入口处先判空”的习惯，放在所有树题里都是通用准则。
返回值方面也要留意：题目要求返回的变量类型是 List<List >，所以初始化用new ArrayList<>()是完全正确的。有些人在空树场景直接返回 null，这在很多题目里会被判错，因为调用方会遍历 result，遇到 null 直接空指针。
3.3 队列快照 for 循环：这层处理的核心
下面这段是整道题的灵魂：
int levelSize = queue.size(); List<Integer> levelList = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { Node node = queue.poll(); levelList.add(node.val); if (node.children != null) { for (Node child : node.children) { queue.offer(child); } } } result.add(levelList);这里我特别想解释一下levelSize的取值时机。它在 while 循环体内、for 循环之前，就通过queue.size()拿到了。为什么要先存一个多少？因为一旦你在 for 循环里开始 offer 孩子节点，队列的 size 就会变化，如果直接用queue.size()作为循环结束条件，就会出现“循环停不下来”或者“把下一层节点混进当前层”的问题。
用levelSize锁定当前层的节点数量，本质上是给“这一层”画了一条终止线。for 循环只从队列里弹出 levelSize 个节点，每弹一个，就把它的孩子们塞到队尾。等 for 循环结束，队列里剩下的内容，就全部是下一层的节点。接着 while 进入第二次迭代，重新快照新的 levelSize，继续处理新的层。这个结构，就是层序遍历的核心节律。
在 for 循环内部，对 N叉树的孩子入队，我加了一个判空：if (node.children != null)。虽然力扣给的测试用例里，几乎不会有某个节点的 children 是 null 的情况——更常见的是空 List——但严谨一点没有坏处，尤其当你的代码被用于真实项目里的树结构时，children 为 null 的可能性是存在的。
queue.offer和queue.add在这里没有本质区别，都是入队。我习惯用 offer，因为它和 poll 配对，语义更队列化，且在真队列容量限制时返回特殊值而不是抛异常。
3.4 层内顺序与结果收集顺序的分析
LeetCode 的判定要求输出顺序是“从左到右”，也就是每一层内，节点按它们在树中的先后位置排列。
我们的代码是怎么保证这一点的？其实都是靠入队顺序。当处理父节点时，for 循环遍历它的 children 列表，是按列表下标顺序逐个 offer 的。队列先进先出，所以下一层节点出队时，必定的也是这个顺序。这个逻辑传递下去，就保证了整棵树的层内从左到右。
如果某人把 children 倒序遍历入队，那结果就会变成从右到左，力扣测试就会判错。所以如果你刷这道题遇到“输出顺序和预期相反”，先检查是不是孩子列表的遍历顺序写反了。
我不止一次在评论区看到有人问“为什么我的结果反了”，十有八九是把for (Node child : node.children)写成了从children.size() - 1倒着遍历。这个错误在二叉树里不明显，但到 N叉树里，因为孩子多，一倒序就整个歪掉。
3.5 复杂度分析与性能表现
时间复杂度：每个节点只会入队一次、出队一次，所以总操作次数是 O(n)，n 是节点总数。这个复杂度是任何层序类题目的最优解。
空间复杂度：队列里同时最大存在的节点数是“某一层的最多节点数”，也就是最宽的那一层。对 N叉树来说，最坏情况是根节点有 N-1 个孩子，那一层的宽度就是 N-1，所以空间复杂度 O(w)，w 是树的最大层宽。如果树退化成一条链，w 约等于 1，空间复杂度就是 O(1)；如果树是一个“章鱼式”结构，根节点拦着一大片叶子，那 w ≈ n，空间复杂度 O(n)。
从力扣的实际测评来看，这个代码在所有节点都在一棵树上的前提下，没有超时的可能，瓶颈只在队列扩容的内存损耗上。实际跑下来，一个 10 万节点的树，执行时间通常在几十毫秒以内，属于非常稳妥的方案。
4. 另一种解法：递归 + 深度号的 DFS 模拟层序
4.1 递归做法能跑通，但很多人想不通为什么
队列迭代是这道题的标准解法，但力扣评论区里总有人贴递归做法，而且用的还是 DFS 的思路。我第一次看到时也愣了一下：DFS 明明是先往深处走，凭什么能做到按层输出？
这里的关键点在于，递归的层序“不是真正的按层访问节点”，而是借用一个 depth 参数来帮忙“占位置”。
先看代码。
class Solution { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> levelOrder(Node root) { if (root == null) { return result; } dfs(root, 0); return result; } private void dfs(Node node, int depth) { if (node == null) { return; } if (result.size() == depth) { result.add(new ArrayList<>()); } result.get(depth).add(node.val); if (node.children != null) { for (Node child : node.children) { dfs(child, depth + 1); } } } }这段代码的逻辑非常精妙。它其实不管“谁先被访问”，只管“你告诉我你在第几层，我就把你放到第几个数组里”。比如它先一路递归到最左下角的节点，即便这个节点在第三层，没关系，它进的是 result 的第三个子数组。等递归回溯回来，再访问同层的其他节点，也放进第三个数组。排序是谁先到谁先排，但不影响分组的正确性。
判断result.size() == depth的意思是：我准备把当前节点放到 depth 层的数组里，但这个数组还没创建，那我就创建一个新的。因为递归是深度优先的，所以当你第一次、第二次这样深入到一个前所未有的深度时，数组必然不够用，需要扩容。这个判断其实是“这一层还没建数组”的信号。
4.2 递归和迭代的取舍
面试场景我一般只写迭代，因为层序遍历的提问意图就是 BFS，面试官想看你队列用的熟不熟练。但递归解法可以作为补充知识，它考察的是“如何用全局变量 + 参数状态模拟过程”，这也是很多回溯题的基本思路。
两种方案的对比我整理成了表格，这里贴一份：
| 对比维度 | 队列迭代法 | 递归模拟法 |
|---|---|---|
| 核心数据结构 | Queue | 调用栈 + 深度参数 |
| 可读性 | 直观，标准模板 | 代码短，但需要理解“占位”思想 |
| 空间占用 | 队列保存当层节点 | 递归栈深度约等于树高 |
| 面试推荐度 | 高 | 中（用于展示思维广度） |
| 出错风险 | 低 | 中（容易忘记创建层数组） |
就这道题而言，迭代法是正统解。我在实际刷题中，是先掌握了迭代法，再回头去玩递归解法的。这么玩下来，对“层”这个东西的理解会更深一层，因为两种方式对这个维度的处理完全不同。
5. 高频错误与边界问题排查实录
刷题和写业务代码一样，一次跑通是少数，大部分时间都花在“看输出为什么错”上面。我把自己和周围人在这道题上踩过的坑集中复盘一下，按出现概率从高到低排序，整理成了一份避坑清单：
| 序号 | 错误现象 | 根因分析 | 解决方案 |
|---|---|---|---|
| 1 | 输出变成了孩子节点和父节点混在一个数组里 | 没有记录 levelSize，直接 while + poll，把整个队列当一层处理了 | 在每层开始前用 queue.size() 做快照 |
| 2 | 编译报错，找不到 left、right 属性 | 拿二叉树的 Node 定义来写 N叉树 | 改用题目提供的 children 列表 |
| 3 | 结果数组的层数和树的实际层数对不上 | 递归解法中 result.get(depth) 之前没有正确扩层 | 判断 result.size() 是否等于 depth，等于就先 add 新数组 |
| 4 | 输出顺序从右到左了 | 孩子节点入队时倒序遍历了 children 列表 | 恢复为正序遍历 |
| 5 | 空树时返回了 null | root == null 分支里直接 return null | 返回 new ArrayList<>() 初始化好的 result |
| 6 | 内存用了很多，接近 O(n) | 在队列里塞入了重复的、已经访问过的节点 | 检查是否存在把同一个节点多次入队的逻辑 |
几个高频错误的细节我给你展开聊聊。
第一个问题“队列快照失效”，是最经典的错法。有些新手直接写：
while (!queue.isEmpty()) { for (int i = 0; i < queue.size(); i++) { // poll and add children } }看起来好像也是 for 循环，但问题在于queue.size()每次循环都会重算。你在循环里一边 poll 一边 offer，队列的大小完全不是最初的形状，循环次数变成一个动态值，层边界直接被破坏。这个时候输出的数组，有的层特别长、有的层特别短，还容易出现空数组。
第二个问题“递归解法结果错位”，这就要理解递归时 depth 和 result.size() 的关系。我见过有人这么写：
result.get(depth).add(node.val);但如果 depth 等于 result.size()，这个位置根本没有数组，直接报 IndexOutOfBoundsException。所以递归解法里那一行if (result.size() == depth)的创建逻辑绝对不能删。也有人把等于号改成大于，结果变成每次多创建一层空数组，最后输出里夹杂一堆[]，力扣一样判错。
第三个问题是相对隐蔽的“多层空数组问题”。出现这种情况，多半是空树处理之后，result 已经被初始化了，但递归里每层判断条件写成了result.size() < depth，导致多出来一个空的 ArrayList。这类问题光看逻辑不好定位，我的习惯是在本地写个 crudely 打印每一层的 size，一眼就能看到空数组所在的位置。
6. 实操经验与这道题的延伸价值
6.1 以这道题为突破口，层序类题目直接打包带走
认真刷完 429 之后，后续几个高频题你完全能低成本地迁移：
- 力扣 102 二叉树的层序遍历：只是把对 children 的遍历换回 left + right，其他一字不改；
- 力扣 107 二叉树的层序遍历 II：输出是自底向上的，只要在最后
Collections.reverse(result)即可； - 力扣 103 二叉树的锯齿形层序遍历：在层序遍历基础上按层号奇偶反转 levelList；
- 力扣 515 在每个树行中找最大值：for 循环里把 val 变成打擂求 max；
- 力扣 116 填充每个节点的下一个右侧节点指针：本质上是层序的指针连接变体。
从这个角度讲，429 就是“层序遍历全家桶”的底层模板。我把这个模板固化下来以后，遇到这类题基本就是十分钟以内的事，剩下的时间都花在读题干和边界处理上。
6.2 我实际刷这道题时的一些小习惯
一是先用例例手推一遍。拿到题目样例，我会把样例的树结构先在纸上画出来，然后模拟队列里节点的变化。三个节点、五个节点的小树，手推两遍后，你对 for + size 的理解会非常牢。
二是不要一上来就写最优解。第 1 遍刷的时候，可以故意不写if (root == null)判断，跑一遍看力扣会不会判错。这个体验式的犯错能加深印象，比只看题解有效得多。
三是把队列操作统一成 offer/poll，不要 add/remove 混着用。刷题的时候很多人不觉得这有什么，但面试手写代码时，混用集合方法会显得不够整洁，而且有些面试官会盯着 API 的语义追问。
四是对力扣默认的 Node 定义保持敏感。这道题的 Node 构造函数有好几个，如果你自己写测试用例时用了new Node(1, children)的构造，那么 children 不能为 null，否则走带参构造函数也会出问题。自己构造测试数据时，建议显式传new ArrayList<>()而不是 null。
6.3 代码规范与命名的小建议
很多算法题代码只用寥寥几个变量，于是有人就写List<List<Integer>> res、Queue<Node> q、int n，这很正常，力扣判题也不在乎变量名。但如果你刷题是为了面试手写，我还是建议把变量名写得可读一点。
我自己刷 429 时，代码里默认用result、queue、levelSize、levelList，这种命名一眼就能看出每个变量的职责。真到面试时，面试官看你代码，不需要你多解释就能读懂，这种隐性好感比任何口头表达都管用。
6.4 关于刷题顺序的延伸建议
如果这是一道你刚开始刷树类题目的入门题，我建议按这个顺序往下走：先做力扣 144 二叉树的前序遍历（递归版），再做 102 层序遍历（迭代版），再做 429 N叉树层序遍历。前序题帮你建立“递归”的概念，层序题帮你建立“队列”的概念，N叉树题帮你建立“孩子列表”的抽象。三步下来，树的两种基本遍历方向算是彻底打通了。
我自己当初是反着刷的——先刷了 N叉树，再回头刷二叉树，结果反而总在 left/right 和 children 之间转换时犯迷糊。后来我把顺序理顺，做题速度提升了一截。先掌握通用的容器和遍历结构，再去套具体的二叉特例，逻辑上确实更顺。
这道题还有一个好玩的点是：N叉树的层序遍历结果，在很多实际业务场景里都有映射，比如公司组织架构的层级展示、文件目录的按层展开、评论区的楼中楼渲染。后台给你的数据往往就是一棵 N叉树，你要在前端把它一层一层展平，核心逻辑和今天这题的 BFS 完全同源。所以刷 429 不是白刷的，哪天你在管理系统里写一个“按层级展开所有部门”的功能，大概率会想起今天这份代码。
