题目描述

给定一个 N 叉树，返回其节点值的层序遍历（即从左到右，逐层访问每一层的所有节点）。

示例输入格式（层序序列化）：

输入示意：

         1/ | \3  2  4/ \5   6

输出：

[[1], [3,2,4], [5,6]]

解题思路

一、什么是层序遍历？

层序遍历即 Breadth-First Search（BFS），按树的“层”来依次访问节点。我们常用一个 队列（Queue） 来实现 BFS 遍历。

二、具体做法

1. 初始化结果集 result 和队列 queue。

2. 将根节点 root 入队。

3. 每次处理一层中的所有节点：

   • 记录当前层节点数量 levelSize。

   • 遍历这些节点，将它们的值加入 levelNode。

   • 同时将这些节点的所有子节点加入队列，供下一层遍历。

4. 重复以上步骤，直到队列为空。

5. 返回 result。

---

Java 代码实现

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> result = new LinkedList<>();Queue<Node> queue = new LinkedList<>();if (root == null)return result;queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> levelNode = new LinkedList<>();for (int i = 0; i < levelSize; i++) {Node node = queue.poll();if (node.children != null) {List<Node> chil = node.children;for (int j = 0; j < chil.size(); j++) {queue.offer(chil.get(j));}}levelNode.add(node.val);}result.add(levelNode);}return result;}
}

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的总数。每个节点只遍历一次。

• 空间复杂度：O(n)，最坏情况下队列中会同时存放所有节点（例如最后一层所有节点）。

---

小结

本题的核心在于使用 BFS 遍历 N 叉树。虽然相较于二叉树多了多个子节点，但思路依然不变 —— 使用队列维护每一层的节点，逐层访问并收集结果。

层序遍历在很多树型结构的题目中都有广泛应用，掌握此类题目是学习树和图的重要基础。