題目描述
給定一個 N 叉樹，返回其節點值的層序遍歷。（即從左到右，逐層遍歷）。
樹的序列化輸入是用層序遍歷，每組子節點都由 null 值分隔（參見示例）。
示例 1：
輸入：root = [1,null,3,2,4,null,5,6]
輸出：[[1],[3,2,4],[5,6]]示例 2：
輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
輸出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示：
樹的高度不會超過 1000
樹的節點總數在 [0, 10^4] 之間
問題分析
這是一道典型的樹的層序遍歷問題。與二叉樹的層序遍歷相比，N叉樹的特點是每個節點可以有任意數量的子節點。
要求：
按照層級順序遍歷樹（從上到下，從左到右）
每一層的節點值要分組返回
需要區分不同的層級
思路：
使用廣度優先搜索（BFS）是最直觀的解法
也可以使用深度優先搜索（DFS），配合層級信息
需要記錄每個節點所在的層級
解題思路
方法一：廣度優先搜索（BFS）
BFS是解決層序遍歷問題的經典方法，因為BFS天然按照層級順序訪問節點。
算法步驟：
使用隊列存儲節點，隊列的特性保證了先進先出的層序訪問
每次處理隊列中的所有節點（即當前層的所有節點）
在處理當前層節點時，將它們的子節點加入隊列（為下一層做準備）
記錄每一層的節點值
優勢：
邏輯直觀，容易理解
代碼結構清晰
時間復雜度優秀
方法二：深度優先搜索（DFS）
DFS通過遞歸的方式遍歷樹，同時記錄當前節點的層級信息。
算法步驟：
遞歸遍歷每個節點
傳遞層級參數，記錄當前節點所在的層
根據層級將節點值放入對應的結果列表中
遞歸處理所有子節點
優勢：
代碼簡潔
不需要額外的隊列數據結構
遞歸思維自然
算法圖解
以示例1為例：root = [1,null,3,2,4,null,5,6]
樹結構：1/ | \3 2 4/ \5 6BFS執行過程：
初始狀態：隊列 = [1]，結果 = []
第1層：
處理節點1，當前層 = [1]
將節點1的子節點加入隊列：隊列 = [3,2,4]
結果 = [[1]]
第2層：
處理節點3,2,4，當前層 = [3,2,4]
將節點3的子節點加入隊列：隊列 = [5,6]
結果 = [[1],[3,2,4]]
第3層：
處理節點5,6，當前層 = [5,6]
沒有子節點，隊列為空
結果 = [[1],[3,2,4],[5,6]]
DFS執行過程：
訪問節點1（level=0）：result[0] = [1]
訪問節點3（level=1）：result[1] = [3]
訪問節點5（level=2）：result[2] = [5]
訪問節點6（level=2）：result[2] = [5,6]
訪問節點2（level=1）：result[1] = [3,2]
訪問節點4（level=1）：result[1] = [3,2,4]
詳細代碼實現
Java 實現
Java N叉樹節點定義
// Java N叉樹節點定義
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;}
}BFS 方法
import java.util.*;class Solution {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 levelSize = queue.size();// 當前層的節點值列表List<Integer> currentLevel = new ArrayList<>();// 處理當前層的所有節點for (int i = 0; i < levelSize; i++) {Node currentNode = queue.poll();currentLevel.add(currentNode.val);// 將當前節點的所有子節點加入隊列if (currentNode.children != null) {for (Node child : currentNode.children) {queue.offer(child);}}}// 將當前層的結果加入最終結果result.add(currentLevel);}return result;}
}DFS 方法
import java.util.*;class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> result = new ArrayList<>();// 邊界條件檢查if (root == null) {return result;}// 從根節點開始DFS，初始層級為0dfs(root, 0, result);return result;}private void dfs(Node node, int level, List<List<Integer>> result) {// 如果是新的層級，需要創建新的列表if (level >= result.size()) {result.add(new ArrayList<>());}// 將當前節點的值加入對應層級的列表result.get(level).add(node.val);// 遞歸處理所有子節點，層級加1if (node.children != null) {for (Node child : node.children) {dfs(child, level + 1, result);}}}
}C# 實現
C# N叉樹節點定義
// C# N叉樹節點定義
public class Node {public int val;public IList<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, IList<Node> _children) {val = _val;children = _children;}
}BFS 方法
using System.Collections.Generic;public class Solution {public IList<IList<int>> LevelOrder(Node root) {IList<IList<int>> result = new List<IList<int>>();// 邊界條件檢查if (root == null) {return result;}// 使用隊列進行廣度優先搜索Queue<Node> queue = new Queue<Node>();queue.Enqueue(root);while (queue.Count > 0) {// 當前層的節點數量int levelSize = queue.Count;// 當前層的節點值列表IList<int> currentLevel = new List<int>();// 處理當前層的所有節點for (int i = 0; i < levelSize; i++) {Node currentNode = queue.Dequeue();currentLevel.Add(currentNode.val);// 將當前節點的所有子節點加入隊列if (currentNode.children != null) {foreach (Node child in currentNode.children) {queue.Enqueue(child);}}}// 將當前層的結果加入最終結果result.Add(currentLevel);}return result;}
}DFS 方法
using System.Collections.Generic;public class Solution {public IList<IList<int>> LevelOrder(Node root) {IList<IList<int>> result = new List<IList<int>>();// 邊界條件檢查if (root == null) {return result;}// 從根節點開始DFS，初始層級為0Dfs(root, 0, result);return result;}private void Dfs(Node node, int level, IList<IList<int>> result) {// 如果是新的層級，需要創建新的列表if (level >= result.Count) {result.Add(new List<int>());}// 將當前節點的值加入對應層級的列表result[level].Add(node.val);// 遞歸處理所有子節點，層級加1if (node.children != null) {foreach (Node child in node.children) {Dfs(child, level + 1, result);}}}
}復雜度分析
BFS方法
時間復雜度：O(n)，其中n是樹中節點的總數。每個節點恰好被訪問一次。
空間復雜度：O(n)，主要是隊列和結果數組的空間開銷。最壞情況下，隊列中可能存儲接近n/2個節點（最底層）。
DFS方法
時間復雜度：O(n)，每個節點恰好被訪問一次。
空間復雜度：O(h)，其中h是樹的高度。主要是遞歸調用棧的深度，最壞情況下為O(n)（退化為鏈狀樹）。
_262)
