N叉树层序遍历全解析：BFS与DFS两种解法及面试加分项

拿到这个题我先说说为什么想专门写一篇博客——leetcode 429在算法题库里属于看一眼就会写一遍就错的典型。你说它难吧N叉树层序遍历无非就是队列出入队你说它简单吧面试时至少有三分之一的候选人会在如何精确控制每一层这个点上卡住甚至写出来的代码连样例都跑不过。作为面试过不少人的老工程师我太清楚这题的定位了它考的不是你背了多少模板而是你有没有真正理解BFS里“层”这个概念的存在形式。这篇文章把我在刷题、面试、辅导别人过程中积累的完整拆解写出来覆盖两种主流解法、边界情况、复杂度分析以及面试现场怎么把这道题讲出加分项。1. 为什么N叉树层序遍历是算法面试里的“性价比之王”先给一个反直觉的结论这道题在面试中的出现频率远高于它在力扣上的难度标签。原因很简单层序遍历牵扯到的知识点非常密集又非常基础——树的结构、队列的使用、层与层之间的边界判定、结果集的构造逻辑全在这一道题里。而且N叉树是二叉树层序遍历的自然延伸面试官从102题改一个Node定义就能快速测出你对“树的遍历”到底是理解了本质还是仅仅记住了二叉树的写法。从数据结构的角度看N叉树的知识结构是这样的每个节点有一个值加上一个孩子列表。这个“孩子列表”就是与二叉树最大的分水岭——二叉树里我们习惯写root.left和root.right到了N叉树你必须统一改写成遍历一个ListNode思维上的惯性很容易导致现场改代码时手忙脚乱。从算法策略的角度看层序遍历有两个完全不同的实现范式迭代式BFS用队列维护“下一批要访问的节点”核心难点是搞清楚当前队列里的节点到底属于哪一层。递归式DFS用深度参数传递当前的层级信息把“层”的概念隐式编码在递归栈里代码更短但需要理解递归与深度的对应关系。这两个范式刚好覆盖了面试里的两种考察方向前者考数据结构的运用后者考递归思维。我个人的建议是如果你时间有限优先把BFS写法练到条件反射的程度但递归写法也必须会因为很多面试官会追问“能不能不用队列实现”这时候DFS解法就是你的第二张底牌。再说这题在面试中的变体潜力——它不是一个孤立的题目而是一个家族的根。层序遍历变形题大概有这么几类之字形打印、每层最大值/平均值、树的宽度、序列化与反序列化、最小深度。你只要把429这一题的层控制逻辑吃透其他变形题只是在拿到每一层之后做点额外处理或改变入队顺序而已。这也是我把它称为“性价比之王”的原因花一题的时间储备十题的弹药。最后一层值得把话说透的是“暴力美学”这个说法到底指什么。层序遍历本质上就是全量遍历 按层归类没有任何巧妙的剪枝或优化空间时间复杂度是绕不开的O(n)。但它的美恰恰在于最朴素的思路配合严格的控制逻辑就能写出正确、简洁、稳定的代码。在某些项目场景里我们追求的从来不是玄学而是可控和确定。树上的层序操作——比如多叉树的地域层级展开、组织架构逐级加载——靠的就是这种“暴力但有效”的办法。2. N叉树与二叉树层序遍历的差异以及题目输入输出到底长什么样先把题面的数据结构看清楚。这道题的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; } }与二叉树节点定义相比最大的变化是left和right两个指针被统一收拢成了children列表。这个小小的改动对代码逻辑的影响是深远的孩子的数量不确定二叉树你永远只需要处理两个分支N叉树必须用循环遍历整个列表。空值的语义更微妙在二叉树里null表示“没有这个孩子”在N叉树里children可能为null也可能是空列表[]处理方式略有不同。层序遍历时的入队逻辑变了二叉树是if (left ! null) queue.offer(left); if (right ! null) queue.offer(right);N叉树则变成一个for循环。再看题目要求的输出格式。层序遍历要求返回的是一个二维列表第一维是层数第二维是这一层从左到右的所有节点值。举例来说如果输入是一棵三层的三叉树根节点值为1它的三个孩子是3、2、4而3又有三个孩子5、6、7那么输出应该是[ [1], [3,2,4], [5,6,7] ]这个输出结构本身就给算法提了一个要求必须在遍历过程中就区分出层的边界否则你只能得到一个一维的扁平列表。换句话说层序号这个概念必须显式或隐式地存在于你的算法里。这也是我接下来要讲的两个解法的分水岭——BFS用队列长度控制层边界DFS用递归深度对应层序号。顺带提醒一个非常容易忽略的细节力扣在测试时会传入root null的情形。这种空树不能返回null而要返回一个空列表[]否则判题直接报错。很多人在本地测试只写了非空用例交上去才发现因为空指针挂掉。我会在后面的边界情况专门展开这个问题。3. BFS队列解法layer size 才是控制层级真正的“定海神针”BFS做层序遍历很多初学者第一反应是“我只要把节点一层层塞进队列就行”。确实队列天然适合做广度优先的横向扩展但入队只解决了遍历顺序问题没有解决“我怎么知道当前出队的节点是哪一层的”这个问题。如果不去控制层边界用同一个队列一路消费下去你得到的就是一个不分层的扁平序列完全不符合题目要求的二维结构。好在这一层边界其实不难确定在遍历每一层之前先看一眼队列当前的长度size这个size就是本层节点的总数。因为队列里的节点永远是“先进入的先出来”而在开始遍历某一层时队列里恰好只包含这一层的所有节点——上一层的节点已经全部出队下一层的节点还没有被加入。于是我们只需要在内部循环里精确执行size次出队操作就能把这层的节点全部处理完。3.1 逐行注释版BFS解法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 size queue.size(); // 本层节点的数量 ListInteger level new ArrayList(); for (int i 0; i size; i) { Node node queue.poll(); level.add(node.val); // 核心把当前节点的所有孩子加入队尾下轮消费 if (node.children ! null) { for (Node child : node.children) { queue.offer(child); } } } result.add(level); // 一层处理完装入结果集 } return result; }这个解法里最关键的一行就是int size queue.size()。它的作用是在本轮循环开始前“拍快照”把当前队列的长度记录下来。为什么要提前记录因为如果在for循环里直接写queue.size()作为循环条件这个值每一轮都在变——每出队一个节点可能又入队好几个孩子循环就永远不会按预期结束。这是一个很多人实际写代码时会踩的坑我在面试中不止一次看到候选人写出了类似for (int i 0; i queue.size(); i)的代码跑出来的结果完全错乱。3.2 另一种层间分隔玩法哨兵节点以及它为什么不如size方案除了size快照法社区里还有一种通过“哨兵节点”分隔层的做法。具体思路是在每一层入队结束后往队列里塞一个特殊标记值比如null消费队列时一旦遇到这个标记就说明这一层结束了。写法大致长这样QueueNode queue new LinkedList(); queue.offer(root); queue.offer(null); // 第一层的结束标记 while (!queue.isEmpty()) { Node node queue.poll(); if (node null) { result.add(level); level new ArrayList(); if (!queue.isEmpty()) { queue.offer(null); // 下一层的结束标记 } } else { level.add(node.val); if (node.children ! null) { queue.addAll(node.children); } } }对这种方案我个人的评价是能跑通但代码的可读性弱而且容易在标记管理上出幺蛾子。比如当队列为空时需要手动判断是否还要再塞标记循环结束的时机也容易算错。相比之下size快照法在逻辑上更直接也更不容易出错所以我强烈建议你在面试中优先用size方案而不是去追求哨兵节点的“花活”。3.3 复杂度分析时间和空间分别花在了哪里时间复杂度O(n)其中n是树上节点总数。每个节点入队一次、出队一次对children列表的遍历总次数也恰好是n-1除根节点外每个节点都是某个父节点的孩子。所以整体是严格的线性复杂度。空间复杂度O(n)。队列中最多同时保存的节点数取决于树的最大宽度。最坏情况下如果这棵树是“宽而扁”的——比如根节点有n-1个孩子——那么第一层处理完后队列里会一次性挤进n-1个节点空间就是O(n)级别。关于空间复杂度我多说一句。有人觉得 BFS 空间占用大不如递归省空间其实这是误解。递归的调用栈在最坏情况下退化成一条链也是O(n)深度本质上并不比队列更省。真正决定空间消耗的是树的结构而不是你选了BFS还是DFS。4. DFS递归解法用depth参数把层序号写进栈帧里面试官如果只想考队列题目到BFS解法就结束了。但很多人不知道层序遍历还有一个完全不同的递归写法而且代码比BFS更短。它的核心洞察是DFS本身的遍历顺序天然就是从左到右的只要我们在递归时把当前深度传下去就能在回溯过程中把节点值填进对应层的列表里。这个思路用一句话总结不需要显式的队列递归栈本身就帮我们保存了“层”的信息。4.1 先序遍历配合深度索引的完整实现class Solution { private ListListInteger result new ArrayList(); public ListListInteger levelOrder(Node root) { 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.size() depth这个判断。因为我们是先序遍历每一层的第一个节点被访问到时该层的列表一定还不存在需要新建而同一层的后续节点再进来时列表已经就位直接往里加就行。这个“列表是否存在”的判断代替了BFS中的size快照本质上都是在标记“层的边界”。用生活化的类比来解释这就像一群人在银行柜台排队取号每个人手里拿到的号就是depth叫号系统每遇到一个新号码段的第一个人就开辟一个新窗口同号段的人陆续过来全部进同一个窗口办理。队列的本质是物理排队递归的本质是发号牌但最终结果一致。4.2 递归解法的使用场景与限制递归方案最大的优点是代码短、容易写尤其适合在纸上手写代码的面试场景。但它也有一个不可忽视的软肋递归深度受栈空间限制。极端情况下如果N叉树退化成了一条深链——每层只有一个节点——递归深度就会达到nJava默认的虚拟机栈很可能在几万层时直接抛出StackOverflowError。所以我的建议是日常刷题、面试讲思路你用递归完全没问题但如果这个层序遍历逻辑要落到生产环境的框架里面对的是不可控的输入数据我会毫不犹豫地选择BFS循环版本。前者是思维上的优雅后者是工程上的稳健两者不冲突但你得知道什么时候该切换。4.3 队列方案和递归方案一张表看清区别对比维度BFS size快照DFS depth参数核心思想用队列显式维护遍历顺序用递归栈隐式携带层级信息层边界控制队列的size快照result.size()与depth比较代码量稍多逻辑更直白精简但需要理解递归栈溢出风险无循环迭代有深树时可能溢出面试加分点考察队列理解是否扎实考察递归与深度参数的关系生产环境推荐度高看数据规模谨慎使用我在面试别人时通常先看候选人能不能给出BFS解法然后追问一句“还能怎么解”。能主动补出DFS解法的候选人至少说明他对“深度”和“层”这两个概念是通透的面试记录里我一般会多加一个正向维度。5. 这些边界情况与隐藏细节才是真正拉开差距的地方从力扣的判题反馈来看很多人不是不会写主逻辑而是在边界处理上翻车。这一节我把经常出问题的细节逐一梳理出来每个都是我在实际刷题或辅导时亲眼见过的错误。5.1 空树与children null的双重防御先看空树。题目要求root null时返回空列表而不是null。这一点在BFS和DFS里都要处理——BFS在函数开头判空直接返回DFS在递归函数里以if (node null) return;作为兜底。两套解法都不能省。再看children为空的场景。力扣的测试用例里叶子节点的children有两种可能null或者空列表[]。你写代码时不能假设它一定是空列表必须在遍历孩子之前判空。一个常见的防御性写法是if (node.children ! null) { for (Node child : node.children) { queue.offer(child); } }有些人为了省一行代码直接queue.addAll(node.children)遇到children null就会抛空指针这也是一个高频翻车点。5.2 单节点树和深层链式树的输出形态只有根节点时输出应该是[[1]]即一个包含一个元素的一层序列。如果用DFS解法result.size()初始为0depth传入0触发新建第一个列表最终得到[[1]]符合预期。链式树每层只有一个节点是递归解法的压力测试。例如一个深度为10000的三叉树但每层只挂一个孩子DFS每次递归只增加一层调用栈深度逼近节点总数Java默认栈大概率扛不住。遇到这种数据BFS解法稳如狗。同层节点的横向顺序题目要求从左到右。BFS入队时按children列表顺序遍历自然保持从左到右DFS在递归孩子时也按列表顺序同样不会乱序。两条路线在顺序语义上是一致的。5.3 手写代码时最容易犯的三个低级错误for循环里用动态的queue.size()作为边界前面已经强调过这是BFS写法里最经典的坑。你在循环里不断出队、入队queue.size()每时每刻都在变化循环轮数完全不可控。把新层的创建放在if (result.size() depth)里却忘了这个判断在空树时也生效如果root null直接进入 DFSdepth还是0result还是空列表那么第一次调用就会创建一个空层并加入结果最终输出了[[]]而不是[]。所以必须在入口处先把空树排除掉。把node.children的列表直接传入队列而没有先判空这在children null时直接炸裂而且报错信息往往发生在几层遍历之后排查起来比一开始就崩更头疼。5.4 队列选型上的一个细节为什么用LinkedList而不是ArrayList层序遍历里我们频繁执行队尾追加、队头弹出两个操作。LinkedList底层是链表头尾操作都是O(1)ArrayList底层是动态数组队头弹出需要把后面所有元素前移单次操作就是O(n)。虽然整体时间复杂度上BFS仍然是O(n)但常数因子差了一个数量级。尤其在最宽的那一层有几千个节点时ArrayList弹出的代价会被放大得非常明显。提示面试时可以随口说一句“这里选择LinkedList是因为它作为队列的入队和出队都是常数时间”这种细节往往是不错的加分点。6. 面试现场实战从“会写代码”到“全场加分”很多候选人有个误区刷题就是刷题代码写完就跑。但真实面试场景里题目只是一个载体面试官真正想看的是你面对未知问题时的分析路径。同样的题目有人拿满分有人只能拿及格差距往往不在代码而在讲解。6.1 拿到题目后的两分钟你应该怎么开口不要一上来就写代码。先和面试官对齐三件事确认数据结构Node 节点里的children会不会为null这决定了后续要不要写防御性判空。确认输出格式空树时返回空列表还是 null层序结果是否需要保持从左到右的顺序确认能否使用辅助空间如果面试官要求O(1)额外空间那说明他希望看到基于递归栈的DFS而不是显式队列。这三句话一说出口面试官对你沟通能力的评估就已经往上走了一档。因为真实的研发协作里接到需求先澄清边界条件是最基本的职业素养。6.2 写完BFS后提前准备几个追问的答案面试官最常见的追问是“如果我想让你输出每层的平均值你怎么改”这其实只动两行代码在BFS每一层循环里累计sum循环结束后除以size。再追问一步“如果想让奇数层从右往左打印呢”你可以在结果生成后对偶数下标或奇数下标的列表做一次Collections.reverse()或者直接在入队顺序上做文章。这些变体题的答案本质上都是基于你已经写好的层控制逻辑做小的加工充分说明把一题吃透远比盲目刷十题更有效。6.3 与二叉树层序遍历的关系面试时直接现场迁移如果你已经刷过二叉树层序遍历力扣102题那么在面试时你完全可以这么说“这道题我从二叉树版本出发把node.left和node.right的单独判断统一改成对children列表的循环遍历其余层控制逻辑完全不变。”这既展示了你对知识迁移的敏感度也为后续代码的可行性提前打了包票。6.4 一些印象深刻的真实考场扣分点根据我观察到的现场表现以下几种情况是高频扣分点写完代码后没有手动模拟一个两层用例。哪怕代码正确面试官也会怀疑你是不是靠背模板写出来的因为你自己都不知道代码每一步在干什么。对“为什么用size快照”解释不清。说明你对BFS的理解停留在背诵层面。空树测试用例没有主动覆盖。真实项目中边界输入永远是最容易出事的地方面试官会把你对空树的敏感性直接投射到工程素养上。反过来能主动在白板上手动演算一遍用例的人几乎都能拿到很好的评价。因为手动演算直接证明了你在意正确性而不是“写完就交差”。7. 从算法题到工程应用多叉树层序遍历在真实项目里的样子说句实在话工作中直接让你写一棵N叉树层序遍历的概率不高但层序遍历的变体在业务代码里非常常见。我举几个实际场景组织架构树逐层加载大公司的组织层级就是一棵多叉树后台管理系统往往需要先加载第一层部门用户点击后再异步加载下一层成员。“逐层加载”这四个字翻译成代码就是BFS里按层控制。多级商品分类的展示电商分类通常是三级或四级的树状结构前端导航栏需要一次请求拿到某一层的所有子分类这同样是“层”的概念。权限树的层级展开权限管理里往往是一棵功能节点树做权限分配时要逐层勾选或展开层序遍历可以直接提供“哪些功能属于同层级”的信息。在这些场景中BFS方案尤为常用因为工程上对树的遍历很少需要递归的优雅更多是追求可控的迭代、清晰的结构、以及对深层数据的稳妥处理。算法题刷到最后你会发现它练的是一种“给数据一个明确结构”的思维能力而这正是做工程最需要的基本功。我在实际项目里多次用过BFS层级控制的小变体——例如批量处理同层级的配置项、对不同层级做不同的权限校验。每次用到都会想起这道题的size快照朴素但可靠。这大概也是为什么它值得被认真吃透而不是当成一道简单的打卡题随便放过。