N-ary Tree Level Order Traversal
Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example, given a 3-ary tree:
We should return its level order traversal:
[ [1], [3,2,4], [5,6] ]
Java Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
// 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;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> myList = new LinkedList<>();
Queue<Node> myQueue = new LinkedList<>();
if(root == null) return myList;
myQueue.add(root);
int currentSize = 1;
int nextSize = 0;
List<Integer> tmpList = new LinkedList<>();
while(!myQueue.isEmpty()){
Node tmp = myQueue.poll();
tmpList.add(tmp.val);
if(tmp.children != null){
for(int i = 0; i < tmp.children.size();i++){
myQueue.add(tmp.children.get(i));
}
nextSize += tmp.children.size();
}
currentSize = currentSize - 1;
if(currentSize == 0){
myList.add(tmpList);
tmpList = new LinkedList<>();
currentSize = nextSize;
nextSize = 0;
}
}
return myList;
}
}
