題目描述

給定一個 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 叉樹。雖然相較于二叉樹多了多個子節點，但思路依然不變 —— 使用隊列維護每一層的節點，逐層訪問并收集結果。

層序遍歷在很多樹型結構的題目中都有廣泛應用，掌握此類題目是學習樹和圖的重要基礎。