N 叉树的层序遍历 图解题解
这道题到底在问什么
- 输入
- 根 1,孩子 [3,2,4];其中 3 的孩子 [5,6]
- 输出
- [[1],[3,2,4],[5,6]]
- 输入
- 单节点 1
- 输出
- [[1]]
最优解：一步一步想明白
- 3记住「当前层整层收下 → 每个节点的 children 整列入队当下一层」,下面逐帧套它。
- 4先找感觉:同一深度的节点是同一层。根 1 是第 0 层,它的孩子 3、2、4 是第 1 层,3 的孩子 5、6 是第 2 层。BFS 就是一层接一层地访问。
- 5进入第 0 层,队列里是 1。这一层先整层收下,再把它们的 children 入队当下一层。
- 6从队首取出 1(橙色高亮),把它的值收进第 0 层,现在本层是 1。
- 71 处理完(变绿)。把它的 children 3、2、4(蓝色)整列加进下一层,目前下一层攒到了 3、2、4。
- 8第 0 层整层收齐 = 1。下一层 3、2、4 已就绪,继续往下。
- 9进入第 1 层,队列里是 3、2、4。这一层先整层收下,再把它们的 children 入队当下一层。
- 10从队首取出 3(橙色高亮),把它的值收进第 1 层,现在本层是 3。
- 113 处理完(变绿)。把它的 children 5、6(蓝色)整列加进下一层,目前下一层攒到了 5、6。
- 12从队首取出 2(橙色高亮),把它的值收进第 1 层,现在本层是 3、2。
- 132 没有孩子(children 为空,变绿),下一层暂时还是 5、6。
- 14从队首取出 4(橙色高亮),把它的值收进第 1 层,现在本层是 3、2、4。
- 154 没有孩子(children 为空,变绿),下一层暂时还是 5、6。
- 16第 1 层整层收齐 = 3、2、4。下一层 5、6 已就绪,继续往下。
- 17进入第 2 层,队列里是 5、6。这一层先整层收下,再把它们的 children 入队当下一层。
- 18从队首取出 5(橙色高亮),把它的值收进第 2 层,现在本层是 5。
- 195 没有孩子(children 为空,变绿),下一层暂时还是 空。
- 20从队首取出 6(橙色高亮),把它的值收进第 2 层,现在本层是 5、6。
- 216 没有孩子(children 为空,变绿),下一层暂时还是 空。
- 22第 2 层整层收齐 = 5、6。没有下一层了,BFS 即将结束。
- 23N 叉树的层序遍历就是 [[1], [3,2,4], [5,6]]:第 0 层 [1]、第 1 层 [3,2,4]、第 2 层 [5,6]。回头看,就是一遍 BFS,每层整层收下、把 children 整列入队,时间 O(n)。
⚠️ 容易写错的地方
✗ 错：把所有值塞进一个列表、不分层
✓ 对：每轮按「当前整层」收成一个子列表
答案要求每层一个列表,必须用「进轮前的队列长度」或「整层取出」来划层边界
✗ 错：只加第一个孩子
✓ 对：把 children 列表整列都入队
N 叉树孩子个数不定,漏加会丢节点;这正是和二叉树(只有左右两个)的区别
✗ 错：忘判空树
✓ 对：root 为空直接返回空列表
不判空会在入队或取值时碰到空指针
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 ansC++
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) { val = _val; }
Node(int _val, vector<Node*> _children) { val = _val; children = _children; }
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (!root) return {};
queue<Node*> q; q.push(root);
vector<vector<int>> ans;
while (!q.empty()) {
vector<int> row;
for (int sz = q.size(); sz--; ) {
Node* n = q.front(); q.pop(); row.push_back(n->val);
for (Node* c : n->children) q.push(c);
}
ans.push_back(row);
}
return ans;
}
};Java
import java.util.*;
class Node {
public int val;
public List<Node> children;
public Node() { children = new ArrayList<>(); }
public Node(int _val) { val = _val; children = new ArrayList<>(); }
public Node(int _val, List<Node> _children) { val = _val; children = _children; }
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
ArrayList<Integer> row = new ArrayList<>();
for (int sz = q.size(); sz > 0; sz--) {
Node n = q.poll(); row.add(n.val);
for (Node c : n.children) q.offer(c);
}
ans.add(row);
}
return ans;
}
}复杂度
时间
O(n)
每个节点恰好入队、出队各一次,n 是节点总数;收集每个值也是常数
空间
O(n)
队列最坏要装下最宽的一层(可达 n 量级);结果数组本身也是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 N 叉树的层序遍历 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用递归(DFS)做层序?+
可以。给递归带一个 depth 参数:访问节点时,若 depth 等于结果列表长度就先新建一层,然后把当前值放进 ans[depth];再对每个孩子用 depth+1 递归。本质是用「层号」把值归到对应层,效果和 BFS 一致,只是遍历顺序是深度优先、靠 depth 归位。
N 叉树层序还能解决哪些变体?+
凡是「按层」的需求都能套这套 BFS:每层的最大值/平均值、N 叉树的最大深度(层数)、之字形层序(偶数层反转)、每层最右节点等。核心都是「队列按层展开」,只把入队孩子改成遍历 children。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 N 叉树的层序遍历 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。