题目描述
思路解析动画文字版
记住「当前层整层收下 → 每个节点的 children 整列入队当下一层」,下面逐帧套它。
什么是层：先找感觉:同一深度的节点是同一层。根 1 是第 0 层,它的孩子 3、2、4 是第 1 层,3 的孩子 5、6 是第 2 层。BFS 就是一层接一层地访问。
第 0 层就位：进入第 0 层,队列里是 1。这一层先整层收下,再把它们的 children 入队当下一层。
第 0 层 · 收值：从队首取出 1(橙色高亮),把它的值收进第 0 层,现在本层是 1。
第 0 层 · 入队 children：1 处理完(变绿)。把它的 children 3、2、4(蓝色)整列加进下一层,目前下一层攒到了 3、2、4。
第 0 层收齐：第 0 层整层收齐 = 1。下一层 3、2、4 已就绪,继续往下。
第 1 层就位：进入第 1 层,队列里是 3、2、4。这一层先整层收下,再把它们的 children 入队当下一层。
第 1 层 · 收值：从队首取出 3(橙色高亮),把它的值收进第 1 层,现在本层是 3。
第 1 层 · 入队 children：3 处理完(变绿)。把它的 children 5、6(蓝色)整列加进下一层,目前下一层攒到了 5、6。
第 1 层 · 收值：从队首取出 2(橙色高亮),把它的值收进第 1 层,现在本层是 3、2。
第 1 层 · 入队 children：2 没有孩子(children 为空,变绿),下一层暂时还是 5、6。
第 1 层 · 收值：从队首取出 4(橙色高亮),把它的值收进第 1 层,现在本层是 3、2、4。
第 1 层 · 入队 children：4 没有孩子(children 为空,变绿),下一层暂时还是 5、6。
第 1 层收齐：第 1 层整层收齐 = 3、2、4。下一层 5、6 已就绪,继续往下。
第 2 层就位：进入第 2 层,队列里是 5、6。这一层先整层收下,再把它们的 children 入队当下一层。
第 2 层 · 收值：从队首取出 5(橙色高亮),把它的值收进第 2 层,现在本层是 5。
第 2 层 · 入队 children：5 没有孩子(children 为空,变绿),下一层暂时还是 空。
第 2 层 · 收值：从队首取出 6(橙色高亮),把它的值收进第 2 层,现在本层是 5、6。
第 2 层 · 入队 children：6 没有孩子(children 为空,变绿),下一层暂时还是 空。
第 2 层收齐：第 2 层整层收齐 = 5、6。没有下一层了,BFS 即将结束。
完成：N 叉树的层序遍历就是 [[1], [3,2,4], [5,6]]:第 0 层 [1]、第 1 层 [3,2,4]、第 2 层 [5,6]。回头看,就是一遍 BFS,每层整层收下、把 children 整列入队,时间 O(n)。
边界:空树返回空、单节点一层、链每层一个。
两个追问:可用带 depth 的 DFS;BFS 框架能解一大类「按层」问题。
参考代码
from typing import Listclass Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else []class Solution: def levelOrder(self, root: 'Node') -> List[List[int]]: if not root: return [] q, ans = [root], [] while q: ans.append([n.val for n in q]) q = [c for n in q for c in n.children] return ans复杂度
- 时间：O(n)，每个节点恰好入队、出队各一次,n 是节点总数;收集每个值也是常数
- 空间：O(n)，队列最坏要装下最宽的一层(可达 n 量级);结果数组本身也是 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能用递归(DFS)做层序?
追问N 叉树层序还能解决哪些变体?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
序列化和反序列化二叉搜索树
LeetCode 449 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题