Cider面试：在本地上写多叉树层序遍历？

多叉树的层序遍历通常使用 **队列（Queue）** 来实现，类似于二叉树的层序遍历。以下是 Java 代码实现： ### **多叉树层序遍历** ```java import java.util.*; class Node { public int val; public List<Node> children; public Node() {} public Node(int val) { this.val = val; this.children = new ArrayList<>(); } public Node(int val, List<Node> children) { this.val = val; this.children = children; } } public class NaryTreeLevelOrderTraversal { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { Node current = queue.poll(); level.add(current.val); if (current.children != null) { queue.addAll(current.children); } } result.add(level); } return result; } // 测试 public static void main(String[] args) { Node root = new Node(1); root.children = Arrays.asList(new Node(3, Arrays.asList(new Node(5), new Node(6))), new Node(2), new Node(4)); NaryTreeLevelOrderTraversal traversal = new NaryTreeLevelOrderTraversal(); System.out.println(traversal.levelOrder(root)); } } ``` ### **Leetcode 题号** 该问题是 **Leetcode 429 题**： 🔗 [Leetcode 429 - N-ary Tree Level Order Traversal](https://leetcode.cn/problems/n-ary-tree-level-order-traversal/) ### **时间复杂度** - **O(N)**，其中 N 是节点数，每个节点入队、出队各一次。 - **O(N)** 空间复杂度（队列 + 结果存储）。