N叉树层序遍历核心解法：BFS队列快照与递归DFS模拟

1. 题目定位与核心思路拆解这道题是我刷力扣时除了二叉树之外第一个觉得“有意思”的层序类题目。力扣429的定位很简单就是让你实现N叉树的层序遍历输出的不是一维数组而是二维数组每一层的结果单独放一个子数组里。我第一次刷的时候第一反应是“这不就是二叉树的层序遍历换了个壳吗”可真上手写了代码才发现坑不多但坑都在看不见的地方。比如孩子节点不是固定的 left 和 right而是放在一个 List 里再比如如果层序遍历的 BFS 模板没有吃透直接把二叉树代码改过来很容易出现“本应是同一层的节点被切成了两个数组”这种其实很隐蔽的结果错误。先说题目本身N叉树的定义是每个节点最多有 N 个孩子而力扣默认的输入是层序序列化的形式但刷题时我们按题目给出的 Node 结构来操作就行不需要自己构建树。核心要求非常明确返回一个 ListList 外层代表层号内层是该层的所有节点值顺序是从左到右。那这道题最大的价值在什么地方呢就是练 BFS 的分层处理能力。层序遍历本身是广度优先搜索的经典场景而“按层输出”这个附加条件恰恰就是算法面试笔试里极高频的考察点——类似“每层平均值”“每层最大值”“锯齿形遍历”都是在它的基础上变种出来的。你把这一题的模板吃透了二叉树、N叉树、甚至图的按层遍历基本就是换皮不换骨。相对适合谁来刷呢我觉得是三类人一是刚学完二叉树、准备系统入门图论的初学者二是准备笔试面试、需要熟练秒杀层序类题目的应届生三是自己写业务代码很少接触树结构、但想补算法基本功的转行工程师。这道题难度属于中等偏下但它考察的是对队列和逐层边界的理解容错率低非常能看出编码功底。2. BFS 的分层逻辑与原理解密2.1 为什么队列天生适合层序遍历层序遍历的本质是按照“离根节点越近越先被访问”的顺序输出节点。要实现这个顺序最直观的数据结构就是队列Queue先进先出。我打个比方你就懂了层序遍历就像一队人排队进电梯。根节点先进电梯出来之前把它的孩子们拉到队尾排队然后第二个节点再进电梯出来时又把它的孩子们排到队尾。整个过程里谁先进去谁先出来你每次读到的节点顺序一定是按层扩散开的。这里有个容易懵的点为什么用栈不行栈是先进后出顺序正好反了会变成深度优先的形态。所以层序遍历的第一原则就是选队列别整花活。力扣上有些人用递归做层序那是用递归强行模拟“层”的概念我后面会讲它的实现逻辑但核心手段仍然是“层号对齐”。2.2 层序输出的核心难点如何确定“这一层”的边界二叉树的层序遍历很多题解上来就写 while for 循环for 循环的次数是当前队列长度但很多初学者不理解这个 for 为什么这么写以及为什么不能用 while (!queue.isEmpty()) 一路 poll 下去。关键就在“边界”二字。BFS 在没有分层标记的情况下它只知道“按顺序访问”并不知道当前访问到的是第几层。如果你只在 while 里做一次 poll那这个循环会一直走到整棵树被访问完输出的结果必然是一维数组因为它根本不知道“该换行了”。那如何让它知道该换行了两个思路分层标记法在队列里塞一个特殊值比如 null作为行尾标识遇到 null 就知道这层结束了队列快照法每次进入下一层之前先记录当前队列的 size这个 size 就是当前层的节点数量然后只从这个数量里 pollpoll 完了这层就结束了。第二个思路是现在的主流做法也是力扣官方题解采用的方式。它的原理很好理解队列里永远只保存“当前层节点的所有孩子”也就是“下一层的完整节点集合”。你在处理当前层之前队列里有多少个节点就代表当前层有多少个节点这个数量是“快照”for 循环就是按这个快照把本层节点全部消费完。我刷题时的一个体会是这个 for size 快照的组合看起来简单但它是所有层序类题目的万能钥匙。你把 for 内部换成求 max、求 sum、处理旋转逻辑换一换代码块就变成了不同的题目。所以这个模板值得专门背下来。2.3 N叉树和二叉树的差异边界二叉树和 N叉树最大的不同就在于孩子节点这个字段。二叉树的节点定义是 left 和 rightN叉树是一个 List children。这导致遍历孩子时你需要一个 for 或者增强 for 循环把当前节点的所有子节点都加入队列。这也是 N叉树唯一一个比二叉树多写代码的地方。其他逻辑包括队列快照、层数组、结果收集完全一模一样。我在第一次改代码的时候犯过一个低级错误直接把二叉树的 left 和 right 入队结果编译直接报错因为 N叉树的节点定义里压根没有这两个属性。这个错犯得很丢人但也提醒我刷题前最好先看清题目给的 Node 定义别凭惯性直接写。3. 核心解法队列迭代实现逐层输出3.1 完整可通过的 Java 实现我平时刷力扣主力语言是 Java先把可以直接提交的完整代码贴出来再逐行讲它在干什么。/* // Definition for a Node. class Node { public int val; public ListNode children; public Node() {} public Node(int _val) { val _val; } public Node(int _val, ListNode _children) { val _val; children _children; } }; */ class Solution { public ListListInteger levelOrder(Node root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); ListInteger 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 为空的隐患就会放大。养成“入口处先判空”的习惯放在所有树题里都是通用准则。返回值方面也要留意题目要求返回的变量类型是 ListList 所以初始化用new ArrayList()是完全正确的。有些人在空树场景直接返回 null这在很多题目里会被判错因为调用方会遍历 result遇到 null 直接空指针。3.3 队列快照 for 循环这层处理的核心下面这段是整道题的灵魂int levelSize queue.size(); ListInteger 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 { ListListInteger result new ArrayList(); public ListListInteger 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空树时返回了 nullroot null 分支里直接 return null返回 new ArrayList() 初始化好的 result6内存用了很多接近 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 代码规范与命名的小建议很多算法题代码只用寥寥几个变量于是有人就写ListListInteger res、QueueNode q、int n这很正常力扣判题也不在乎变量名。但如果你刷题是为了面试手写我还是建议把变量名写得可读一点。我自己刷 429 时代码里默认用result、queue、levelSize、levelList这种命名一眼就能看出每个变量的职责。真到面试时面试官看你代码不需要你多解释就能读懂这种隐性好感比任何口头表达都管用。6.4 关于刷题顺序的延伸建议如果这是一道你刚开始刷树类题目的入门题我建议按这个顺序往下走先做力扣 144 二叉树的前序遍历递归版再做 102 层序遍历迭代版再做 429 N叉树层序遍历。前序题帮你建立“递归”的概念层序题帮你建立“队列”的概念N叉树题帮你建立“孩子列表”的抽象。三步下来树的两种基本遍历方向算是彻底打通了。我自己当初是反着刷的——先刷了 N叉树再回头刷二叉树结果反而总在 left/right 和 children 之间转换时犯迷糊。后来我把顺序理顺做题速度提升了一截。先掌握通用的容器和遍历结构再去套具体的二叉特例逻辑上确实更顺。这道题还有一个好玩的点是N叉树的层序遍历结果在很多实际业务场景里都有映射比如公司组织架构的层级展示、文件目录的按层展开、评论区的楼中楼渲染。后台给你的数据往往就是一棵 N叉树你要在前端把它一层一层展平核心逻辑和今天这题的 BFS 完全同源。所以刷 429 不是白刷的哪天你在管理系统里写一个“按层级展开所有部门”的功能大概率会想起今天这份代码。