LeetCode 429 N-ary Tree Level Order Traversal
摘要：
給予一顆N 叉樹
，返回所有節點的層級遍歷，即從左至右(逐層).
例 :
給予樹:
1
/ | \
324
/ \
56
返回:
[
[1]，
...
給予一顆N 叉樹
，返回所有節點的層級遍歷，即從左至右(逐層).
例 :
給予樹: 1 / | \ 324 / \ 56 返回: [ [1]， [3,2,4] [5,6] ]
解法
該題的要點是保持左右順序，和記錄當前層數，保持順序的意思是指要將樹某一層的資料從左至右放置到陣列中，記錄層數就更不用說了，每一層對應一個數組，要能區分資料的層級。
保持順序這一點我們可以使用佇列來實現，先進先出，獲取到某一節點的左右子節點後，將其所有子節點依次新增到佇列中，這樣可以保證從左至右的順序。
記錄層級這一點，可以先記錄佇列中所有的元素，這個個數就是當前層的個數，哪怕在遍歷過程中向佇列中再添加了下一層的東西，也無所謂，因為我們知道遍歷到多少個就應該換層了。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
public class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result= new ArrayList<>();
if (root != null) {
Queue<Node> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.remove();
list.add(node.val);
if (node.children == null) {
continue;
}
queue.addAll(node.children);
}
result.add(list);
}
}
return result;
}
}
Runtime: 2 ms, faster than 93.07% of Java online submissions for N-ary Tree Level Order Traversal. Memory Usage: 46.8 MB, less than 86.23% of Java online submissions for N-ary Tree Level Order Traversal.