1. 内容整体设计与思路拆解1.1 这道题到底在考什么先说说这道题的定位。LeetCode 429 题N 叉树的层序遍历在二叉树的层序遍历基础上把每个节点最多两个孩子这件事扩展成了“每个节点最多 N 个孩子”除此之外核心逻辑几乎一模一样。很多人第一次看到 N 叉树第一反应是“这题是不是很难”但实际上真不是。树结构相关的算法题往往不是考察你有多聪明的脑洞而是考察你对遍历框架的熟悉程度。你能不能在 10 秒内从“层序遍历”这四个字直接映射到“BFS 队列”这个固定组合这比你能不能徒手写出一个红黑树重要得多。这个题适合谁刷正在准备校招、实习面试的同学尤其是目标岗位是后端开发、客户端开发、测开这类需要手写代码的岗位这道题属于必须掌握的入门偏中档题。它并不难但如果你连递归的两种 DFS 写法和迭代的 BFS 写法都分不清那面试官大概会在你写完这题后追加一道“那你能不用队列实现吗”的追问直接把难度拉满。1.2 为什么 BFS 是层序遍历的默认答案先问一个问题什么叫做“层序遍历”按层从上到下每一层从左到右依次访问所有节点。这句话听起来很简单但如果你拿递归去实现就会发现天然的劣势——递归天生是深度优先的它会把一条分支走到黑然后回头再走另一条分支。所以说BFS广度优先搜索是层序遍历最自然、最符合直觉的解法。BFS 的核心数据结构是队列先进先出。从一个根节点出发先把根节点放进队列然后循环出队一个节点把这个节点的所有子节点依次入队。这个过程听起来像排队打饭。你站在队伍最前面打完饭走人与此同时你身后又排进来几个人队伍继续往后走。最终每个人都按“排队的先后顺序”打完饭而这个顺序恰好就是从上到下、从左到右的层序。这个类比虽然朴素但它直接点破了 BFS 的本质队列保证了访问顺序的公平性——先来的节点先被处理后来的节点排在后面。1.3 从二叉树到 N 叉树变化在哪里如果你已经刷过二叉树的层序遍历比如 LeetCode 102 题那这道 429 对你来说几乎是送分题。唯一的区别在于二叉树用node.left和node.right取子节点N 叉树用node.children取一个子节点列表。代码上的变化就一句话把if node.left: queue.append(node.left) if node.right: queue.append(node.right)换成for child in node.children: queue.append(child)剩下的逻辑——队列初始化、按层记录宽度、清空临时列表——完全一样。不过如果只是简单地说“题很简单”写这篇笔记就没什么价值了。我在实际刷题和带新人复盘的时候发现大家在这道题上真正容易丢分的地方反而不是“会不会写 BFS”而是下面这些细节不会处理null根节点忘记按层分组最后输出一个一维数组而不是二维数组不知道children可能为空列表但空列表和null是不同的处理逻辑用递归实现时depth 参数传错了位置导致某一层数据错乱面试官追问“不用队列怎么做”时直接懵住。这些都是后面要展开讲的内容。2. 核心细节解析与实操要点2.1 题目输入输出的隐藏信息LeetCode 429 的输入是一个Node对象。题目通常给出这样的定义class Node: def __init__(self, valNone, childrenNone): self.val val self.children children注意这里的children是一个列表列表里每个元素都是Node类型。有些语言里children默认是None有些语言里默认是空数组[]。你在本地自测时经常会遇到childrenNone的情况而在 LeetCode 平台上测试数据一般会保证非空。这就带来一个非常实际的坑如果你在代码里直接写for child in node.children:当node.children是None时直接抛TypeError: NoneType object is not iterable。虽然 LeetCode 的评测数据可能不会触发这个错误但你自己构造测试用例的时候几乎一定会踩上。所以我在写题解时习惯加上一行保险if node.children: for child in node.children: queue.append(child)或者更规范的写法for child in (node.children or []): queue.append(child)这两行代码不仅让程序更健壮也让你在面试中显得更专业——你考虑到了边界情况而不仅是“把题跑通就行”。2.2 返回值的结构决定你的代码结构这道题的返回值是List[List[int]]也就是一个二维数组。每一层对应一个一维数组数组里的数字是该层所有节点的值从左到右排列。这个返回值结构直接决定了 BFS 的写法里必须在循环内再套一层循环。你不能像最朴素的 BFS 那样只用一个while queue循环出队一个处理一个否则你得到的是一个一维序列而没法把它们按层切分。正确的做法是在每一轮循环里先读取当前队列的长度size len(queue)然后连续出队size次。这size个节点就是同一层的所有节点。这里有一个点很多人第一次不理解为什么不能在出队的时候动态判断队列长度因为队列是动态变化的。你在出队一个节点的同时又把它的孩子不停入队。如果边出队边取len(queue)那这个长度会随着孩子的入队不断变化你根本没法确定“这一层”的边界在哪里。打个比方你站在自助餐厅门口数人数。一开始队伍有 10 个人你开始一个一个放进去。但每放进去一个人他身后的朋友又跑来排队了队伍长度永远在变你永远数不到 10 这个数。所以必须先“拍照定格”当前长度再按这个长度循环。2.3 什么时候用递归什么时候用迭代看到这里可能有读者会有疑问层序遍历不是也可以用递归吗严格来说可以。如果你往递归函数里传一个depth参数每访问一个节点就把它放到result[depth]这个列表里那么递归结束后result就是一个按层分组的二维数组。代码大概长这样def traverse(node, depth): if not node: return if len(result) depth: result.append([]) result[depth].append(node.val) for child in (node.children or []): traverse(child, depth 1)这段代码也能跑通而且逻辑很简洁。但我想说的是面试中如果考官让你写层序遍历默认答案应该是 BFS 迭代而不是递归。原因有两个。第一递归本质是 DFS。你是“碰巧”利用深度信息完成了“按层分组”但访问节点的顺序并不是严格的层序。比如在第三层你可能是先访问了左子树深处的节点再访问右子树深处的节点只不过最终因为按深度归类输出结果看起来是正确的。但如果你在递归中打印访问顺序你会看到它跟层序并不一致。第二递归的缺点在于树的深度。如果树的深度极端——比如一个 N 叉树退化成链表——递归栈可能会爆掉。在面试场景下迭代 BFS 永远比递归更稳。所以我的建议是这道题别整花活就老老实实写 BFS。面试官要的并不是“你会多少种解法”而是“你能不能把最合适的解法写得滴水不漏”。3. 实操过程与核心环节实现3.1 题解代码Python 版本逐行拆解直接上代码。这是我个人在刷题时最常用的写法简洁、清晰、不绕弯。from collections import deque from typing import List, Optional class Solution: def levelOrder(self, root: Optional[Node]) - List[List[int]]: if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.children: for child in node.children: queue.append(child) result.append(current_level) return result分段拆开看。第一段if not root: return []。这一步是防御性处理。root为None时直接返回空列表。没有这行后面所有逻辑都会崩。实际上很多人在本地跑测试时一旦测试数据是空树就报AttributeError十有八九就是漏了这行。第二段queue deque([root])。这里我用了collections.deque而不是普通列表。原因很实际deque的popleft()是 O(1) 操作普通列表的pop(0)是 O(n) 操作。虽然 LeetCode 的测试数据不至于因为这点差异超时但工程上好习惯要养起来。第三段while queue:是 BFS 的主循环。只要队列不为空就说明还有节点没被访问。第四段level_size len(queue)。这里拍的“快照”是整层的宽度是本解法的关键。它决定了这一轮循环要处理的节点数量。第五段for _ in range(level_size)。这个内部循环负责把当前层的所有节点全部出队并把它们的子节点全部入队。等这个循环结束当前层就已经处理完了队列里剩下的全是下一层的节点。第六段如果node.children不为空就遍历它把所有子节点追加到队列尾部。第七段result.append(current_level)。把当前层收集到的所有节点值作为一个列表加到结果里。最终返回result二维数组每一层对应一个列表。3.2 题解代码Java 版本面试手写模板Java 版本的思路完全一样但有几个细节要注意。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 size queue.size(); ListInteger currentLevel new ArrayList(); for (int i 0; i size; i) { Node node queue.poll(); currentLevel.add(node.val); if (node.children ! null) { for (Node child : node.children) { queue.offer(child); } } } result.add(currentLevel); } return result; } }这里用LinkedList实现队列offer和poll是队列接口的标准操作。在 Java 里Queue接口虽然也有add和remove但这两者在队列已满或为空时会抛出异常而offer和poll会返回特殊值false或null。面试时用offer和poll比add和remove更安全也显得你更懂 API 设计背后的意图。另一个 Java 细节这道题给的节点定义通常长这样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; } }注意children是ListNode不是数组。所以遍历时直接用增强 for 循环就行不需要处理数组下标。3.3 进阶思考不用队列能实现层序遍历吗面试官最爱问的追加问题之一就是你不用队列能不能层序遍历这个问题的意图很明显他想看你是否真的理解了“层序遍历”的本质而不仅仅停留在“套模板”阶段。答案是可以但效率不如队列。一种不用队列的思路是先算出这棵树的层数或最大深度然后对每一层写一个递归函数把所有深度等于target_depth的节点收集起来。伪代码如下def collect_at_depth(node, current_depth, target_depth, collected): if not node: return if current_depth target_depth: collected.append(node.val) return for child in (node.children or []): collect_at_depth(child, current_depth 1, target_depth, collected) def level_order_without_queue(root): depth max_depth(root) result [] for d in range(depth): collected [] collect_at_depth(root, 0, d, collected) result.append(collected) return result这个方法能跑但时间复杂度是 O(n²)——最坏情况下每一层都要把整棵树访问一遍。如果树有 n 层每层递归访问 n 个节点总复杂度就是 n 的平方。这个解法可以作为“思维拓展”讲给面试官听展示你理解多种方案但最终要落地的还是 BFS。因为面试官问这个问题的目的大概率是想引导你对比时间复杂度和空间复杂度而不是真的让你在生产环境里写一个 O(n²) 的层序遍历。3.4 复杂度分析别只会写代码不会说原理在面试中代码写完只是第一步紧接着必问的就是时间复杂度多少空间复杂度多少BFS 版层序遍历的时间复杂度是 O(n)n 是树中节点的总数。每个节点恰好入队一次、出队一次入队出队都是 O(1)所以总时间正比于节点总数。空间复杂度稍微复杂一点。队列中最多同时保存多少节点答案是某一层中节点数量的最大值也就是“最大层宽度”。在最坏情况下比如一棵满 N 叉树最底层可能有 n/2 个节点所以空间复杂度是 O(n)。这个 n 是理论上限不是平均值所以回答时要说“最坏情况下 O(n)”而不是“平均 O(logn)”。很多人会把空间复杂度和二叉树递归遍历的空间复杂度搞混。递归版本的空间复杂度是 O(h)h 是树高因为递归调用栈的深度等于树高。BFS 版本的空间复杂度是 O(w)w 是最大层宽度。两者在不同形态的树面前各有优劣——细长型的树递归更省空间宽胖型的树BFS 更省空间。这个对比如果能在面试中讲出来观感会很不一样。4. 常见问题与排查技巧实录4.1 “我明明按模板写了为什么输出顺序不对”这个问题我见过不少次。代码逻辑看起来没问题但输出结果的层级顺序是乱的。排查思路先把树的结构画出来。N 叉树节点的children列表顺序就是你要访问的子节点顺序。如果题目给的输入是root [1,null,3,2,4,null,5,6]对应的树结构是根节点 1有 3 个子节点3、2、4。节点 3 又有两个子节点5、6。正确层序输出是[[1], [3, 2, 4], [5, 6]]如果你发现输出变成了[[1], [5, 6, 2, 4]]之类的顺序那问题大概率出在你把children顺序搞反了或者你在递归时先访问了子树深处的节点再访问兄弟节点。解决办法很简单回到 BFS 的“队列先入先出”逻辑严格保证“先入队的节点先出队”不要在中途做任何逆序操作。4.2 根节点是 null 时的边界处理LeetCode 的测试用例里可能包含root []这种情况。输入是一个空树预期输出是[]。很多人会在这里跌一跤如果不做if not root: return []的判断代码会在queue deque([root])这一行创建包含一个None的队列然后进入循环后尝试访问node.val直接AttributeError。这种错误非常不优雅在白板面试中一旦发生会严重影响印象分。所以边界判断一定是第一步就写。4.3 children 为空但结果里出现空列表还有一种情况树不是空树但某一层确实没有节点比如所有叶子节点的children都是空列表。这时候如果代码写成if node.children is not None: for child in node.children: queue.append(child)在children是[]而不是None的情况下这个循环不会进入所以不会向队列添加任何节点也不会产生空层。但如果你的写法是if node.children: queue.extend(node.children)[]被视为 False循环同样不会执行。这两种写法都能正确处理空列表。真正的问题出现在另一种写法if len(node.children) 0: queue.append(None)有人为了避免childrenNone出错强行把空列表当成一个特殊节点入队这会导致队列里塞进None后面处理时又得各种判断纯属给自己添乱。4.4 不使用 collections.deque 会怎样如果你真的用普通 list 写queue [root] while queue: node queue.pop(0)在 LeetCode 上大概率也能通过因为测试数据的节点数量没多到让 O(n) 的pop(0)成为性能瓶颈。但当你以后面对真实业务场景处理大规模数据时这种写法会明显拖慢速度。更重要的是在面试中用普通 list 模拟队列在出队操作上不是最优解面试官有理由质疑你数据结构功底不扎实。所以别偷懒Python 用dequeJava 用LinkedList这是标准答案。4.5 实战现场我在本地跑测试时踩过的坑拿到这道题后我第一次在本地测试的代码长这样class Node: def __init__(self, valNone, childrenNone): self.val val self.children children然后我按照 LeetCode 输入格式手动建树node5 Node(5) node6 Node(6) node3 Node(3, [node5, node6]) node2 Node(2) node4 Node(4) root Node(1, [node3, node2, node4])这里没问题但问题出在我写children参数时漏写了默认值导致后面遍历时出现AttributeError: NoneType object has no attribute val。这个错误让我花了五分钟排查。最后才发现是Node(5)没有传children导致默认值为None然后在 BFS 循环里访问node.children时for child in None直接报错。这个坑非常适合作为经验分享在本地构造测试数据时一定要记得给每个叶子节点的children赋默认空列表或者在代码里做空值保护。两种方式选一种就行推荐在代码里做保护因为你不能保证后续所有调用方都按你的预期传参。4.6 刷题心得这道题在面试中的实际定位说实话429 并不是一道压轴难题。它的难度在 LeetCode 里算中等偏低大多数本科生刷题两周后都能独立写出 BFS 解法。但正因为它简单面试官才有机会在你身上挖掘更多信息。我见过一些候选人这道题写得很顺但一被追问“为什么空间复杂度是 O(n) 而不是 O(logn)”就开始支支吾吾也有候选人代码几分钟写完了但让他解释一下level_size为什么要快照他说“这是套路”。这两种回答都暴露了一个问题不是不会写代码而是不理解代码背后的数据结构和算法逻辑。面试不是做题比赛。面试官看的是你解决问题的思维方式遇到一个具体的树结构能不能拆解成“访问顺序”和“分组边界”两个子问题然后分别用队列和快照机制解决。所以与其纠结自己能不能把这道题默写出来不如把 BFS 的每一个细节吃透。这才是“剑斩 OFFER”的意义——不是背题而是通过简单题建立起对算法结构的敏锐度。5. 横向延伸从 429 看 N 叉树的通用遍历法5.1 一个模板通吃前序、后序、层序N 叉树虽然节点多了些但遍历框架跟二叉树完全一致。如果你已经掌握了二叉树的 DFS 和 BFSN 叉树根本不需要额外学。前序遍历的递归模板def preorder(node): if not node: return visit(node) for child in (node.children or []): preorder(child)后序遍历的递归模板def postorder(node): if not node: return for child in (node.children or []): postorder(child) visit(node)注意区别前序遍历是先访问节点再遍历子节点后序遍历是先遍历子节点再访问节点。就这么一层顺序上的差异代表了两种完全不同的访问策略。而层序遍历就是我们这篇笔记主题里反复强调的 BFS 模板def level_order(root): if not root: return [] queue deque([root]) result [] while queue: level_size len(queue) cur [] for _ in range(level_size): node queue.popleft() cur.append(node.val) for child in (node.children or []): queue.append(child) result.append(cur) return result这三个模板是 N 叉树所有遍历题型的地基。5.2 一些相关的题目推荐按什么顺序刷如果你打算把 N 叉树这块吃透建议按这个顺序刷LeetCode 589N 叉树的前序遍历LeetCode 590N 叉树的后序遍历LeetCode 429N 叉树的层序遍历LeetCode 102二叉树的层序遍历BFS 模板源头LeetCode 107二叉树的层序遍历 II从底向上其实就是反转 resultLeetCode 199二叉树的右视图BFS 变体取每层最后一个节点这几道题刷完你对“层序遍历”这个词的敏感度会高很多。以后看到“右视图”“自底向上”“之字形遍历”这类题目脑子里马上能反应出来先 BFS 分层再对结果做加工。5.3 什么时候该想到递归而不是 BFS虽然层序遍历默认 BFS但如果你遇到的是“求树的最大深度”“判断树是否对称”这类问题BFS 反而可能不如递归直观。最典型的例子LeetCode 104二叉树的最大深度。递归版def maxDepth(root): if not root: return 0 return 1 max(maxDepth(child) for child in (root.children or []))五行代码搞定本质是“树的高度 1 子树的最大高度”。这种问题你用 BFS 做也能做但代码明显更长思维也更绕。所以选择递归还是迭代不是机械的“DFS 用递归、BFS 用迭代”而是看哪种解法更能反映问题本身的递归结构。5.4 一道隐藏在 429 背后的真实面试场景我在带人模拟面试时给面试者出过一道基于 429 的变体把 N 叉树的每一层节点值倒序输出。要求不能先正常层序遍历再反转result必须在遍历过程中就实现倒序。面试者一开始毫无思路我提示他倒序的本质是什么倒序的本质不是取反而是“先访问最右边的节点再访问左边的节点”。在 N 叉树里每一层的子节点是按children列表顺序排列的。如果你在 BFS 上一层节点时不是从左到右遍历children而是从右到左遍历那下一层入队的顺序就自然反了。这个变体很好地体现了“对模板的理解程度”。如果只会套模板遇到这种改动可能就懵了如果把“层序 队列顺序 子节点入队顺序”这两件事拆开就会觉得这种题不过是顺手改一个循环方向。所以 429 作为基础题的价值不在于它本身能给你的简历增加什么亮点而在于它帮你建立起一套树的遍历思维框架而框架中的每一个变量——队列、快照、孩子入队顺序——都可以在真实场景中做文章。6. 一点个人经验谈刷到 429 这道题是不少人算法之路上的“舒适区验证题”。如果你 102 题二叉树层序遍历已经吃透这道题基本就是换个皮如果你连 102 都没写过那建议先停下来把二叉树的 BFS 模板写熟再来碰 N 叉树。我自己的经验是每次刷树相关的题都不要满足于“AC 了就下一题”。大概率面试官不会直接拿原题考你而是会出各种变体——右视图、锯齿形层序、层内分组再聚合。这些变体的核心都是 BFS 分层而你真正需要掌握的就是level_size这个快照的语义。在做这题时还可以顺手练一件事把递归版的 DFS 层序也写一遍。你不用把它当成最优解但写过一遍之后你会彻底明白为什么 BFS 更适合做层序——因为递归版虽然也能输出正确结果但它绕了一个大弯。最后一个小技巧送给大家在本地调试时把树的每一层打印成一行的循环同时打印queue的长度变化你能非常直观地看到“每层快照”到底做了什么。这个动态过程看一次比空想十遍都管用。刷题这种事光看永远不够一定要亲手敲一遍代码亲眼看到队列的进出变化才算真正把这道题嚼碎了。祝各位刷题顺利面试场上遇到 429 这一类的题都能稳稳拿下。