LeetCode 429. N 叉树的层序遍历
题目描述
题意分析
从根开始逐层收集节点值，每层单独放入一个列表，同层保持从左到右的顺序。N 叉树的每个节点都有一个孩子列表，可能为空，也可能包含多个孩子。
输入中的
null用于分隔序列化时的孩子分组；函数收到的已经是树节点，无需处理这些分隔符，只需依次遍历children。
解法：队列分层 BFS
核心思路
[!blue]
队列的先进先出顺序适合按层遍历。开始时只有根节点，构成第一层；假设某轮开始时，队列恰好保存当前层从左到右的全部节点，先将它的长度固定为
size。本轮只弹出这
size个节点，将它们的值加入当前层结果，同时把每个节点的孩子按列表顺序加入队尾。处理过程中，队列前半部分是当前层尚未访问的节点，后半部分是已经发现的下一层节点；固定处理数量才能把两层分开。当前层父节点按从左到右的顺序出队，每个父节点的孩子也按从左到右的顺序入队，因此这轮结束时，队列恰好保存下一层从左到右的全部节点。这个性质逐层保持，就得到正确的层序结果。
树中除根以外的每个节点只有一个父节点，会且只会被父节点加入队列一次，不需要额外的访问标记。叶子没有孩子，不会追加节点；队列最终为空时，整棵树已经遍历完。
解题步骤
- 根节点为空时直接返回空结果。
- 将根节点入队。
- 每轮先保存
size = queue.size()，创建当前层结果。- 弹出恰好
size个节点，记录其值，并把所有孩子按顺序入队。- 将当前层加入答案，直到队列为空。
每轮都新建
level，只保存这一层的值。空树在入队前返回空结果；只有根节点时执行一轮即可结束。
代码实现
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> answer = new ArrayList<>();
if (root == null) {
return answer;
}
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
// 只处理本层原有节点，随后追加的孩子属于下一层。
int size = queue.size();
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
Node node = queue.poll();
level.add(node.val);
for (Node child : node.children) {
queue.offer(child);
}
}
answer.add(level);
}
return answer;
}
}
func levelOrder(root *Node) [][]int {
if root == nil {
return [][]int{}
}
answer := make([][]int, 0)
queue := []*Node{
root,
}
for len(queue) > 0 {
// 只处理本层原有节点，随后追加的孩子属于下一层。
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
queue = append(queue, node.Children...)
}
answer = append(answer, level)
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，其中
n为节点数。每个节点恰好入队、出队一次；非空树所有孩子列表的总长度为n-1，嵌套遍历孩子不会变成平方复杂度。- 空间复杂度：$O(w)$，其中
w是树的最大层宽。队列至多同时包含相邻两层的一部分，总量不超过2w；当前层列表也至多有w个值，返回结果不计入额外空间。
关键点总结
[!green]
- 每轮开始时记录的队列长度，就是当前层的节点数。
- 按父节点顺序、孩子列表顺序入队，才能保持下一层从左到右。
- N 叉树与二叉树的分层方式相同，只需将固定左右孩子改为遍历孩子列表。
易错点总结
[!yellow]
- 内层循环不能动态读取队列长度：出队和追加孩子都会改变它，可能提前结束或把下一层混入本层。
- 不能让多个结果项共享同一个可变
level，否则后续修改会影响已经记录的层。- 空树返回
[]，不要把空根入队，也不要额外记录一个空层。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 分层BFS相同，只需把固定左右孩子改为遍历children列表。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！