429. N 叉樹的層序遍歷

給定一個 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]?之間

解題思路

我們使用隊列實現層序遍歷，因為如果使用 ArrayList 的話，我們刪除元素需要 O(n) 的時間復雜度。而隊列刪除元素只需要 O(1)的時間。

并且在while?循環體開始時記錄隊列的當前大小?size。然后用另一個循環來處理?size?數量的節點，這樣我們就可以保證我們每次使隊列出隊的都是位于同一層的節點，并且后面入隊的節點也全是位于當前層的下一層，保證?了while?循環在每一次迭代處理一層。而傳統層序遍歷是加入左右節點的，而這個題目里面我們是需要加入一個list的子節點，所以我們需要再使用一個循環把整個list的子節點入隊。

代碼

/*
// 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) {Queue<Node>queue=new LinkedList<>();queue.add(root);List<List<Integer>> res=new ArrayList<>(); if(root==null) return res;while(!queue.isEmpty()){int size=queue.size();List<Integer> list=new ArrayList<>();for(int i=0;i<size;i++){Node node=queue.poll();list.add(node.val);for(Node cur:node.children)queue.add(cur);}res.add(list);}return res;}
}

• 時間復雜度：O(n)。n?指的是節點的數量。
• 空間復雜度：O(n)。