N-ary Tree Preorder Traversal
Given an n-ary tree, return the preorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
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
// 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 {
List<Integer> myList;
Solution(){
myList = new LinkedList<>();
}
public List<Integer> preorder(Node root) {
reversePreorder(root);
return myList;
}
private void reversePreorder(Node root){
if(root == null) return;
if(root.children == null){
myList.add(root.val);
}
else{
myList.add(root.val);
for(Node ele: root.children){
reversePreorder(ele);
}
}
}
}
//Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public List<Integer> preorder(Node root) {
Deque<Node> myDequeue = new LinkedList<>();
List<Integer> myList = new LinkedList<>();
if(root == null) return myList;
myDequeue.addFirst(root);
while(!myDequeue.isEmpty()){
Node tmp = myDequeue.pollFirst();
myList.add(tmp.val);
if(tmp.children != null){
Collections.reverse(tmp.children);
for(Node ele: tmp.children){
myDequeue.addFirst(ele);
}
}
}
return myList;
}
}
