DeepSeek LeetCode 429. N 叉树的层序遍历 Java实现

LeetCode 429. N 叉树的层序遍历

思路：BFS 队列 + 分层记录

核心思路： 用队列做广度优先遍历。每次处理一层时，先记录当前队列长度 size（这就是本层节点数），然后循环 size 次：出队一个节点、把它的值加入本层列表、把它的所有孩子入队。这样自然保证每层的结果收集到同一个子列表里。

/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val) {
val = _val;
}

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> queue = new LinkedList<>();
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);
// 把当前节点的所有孩子入队（进入下一层）
if (node.children != null) {
for (Node child : node.children) {
queue.offer(child);
}
}
}
ans.add(level);
}
return ans;
}
}

复杂度分析

· 时间复杂度：O(n)，每个节点恰好入队、出队一次。
· 空间复杂度：O(n)，队列在最宽一层最多存放该层节点数，最坏为 O(n)；结果列表本身也占 O(n)。

关键点

对比其他写法

方式 特点
BFS + size（本解法） 最标准、最直观，O(n)
DFS + 层号 递归时 depth 即结果下标，ans.get(depth).add(…)，需要先判断/创建列表；少用队列，但可读性稍差
两个队列交替 用 cur / next 两个队列分别存当前层和下一层，思路等价但空间稍多

面试时用 BFS + size 写法即可，这是 N 叉树层序遍历的标准模板，同样适用于二叉树 102 题。