-
Notifications
You must be signed in to change notification settings - Fork 2
/
PostOrder.java
88 lines (82 loc) · 2.42 KB
/
PostOrder.java
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package n_array;
import utils.Node;
import java.util.*;
/**
* 590. N-ary Tree Postorder Traversal
* Given an n-ary tree, return the postorder traversal of its nodes' values.
*
* Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
*
*
*
* Follow up:
*
* Recursive solution is trivial, could you do it iteratively?
*
*
*
* Example 1:
*
*
*
* Input: root = [1,null,3,2,4,null,5,6]
* Output: [5,6,3,2,4,1]
*
* IMP-3: Simple question, good to practice for tree traversal.
*/
public class PostOrder {
/**
* this is a beautiful approach. mentally think of adding to the beginning of output list instead of the end
* similarly add last child on top of stack so that is the next to be processed as it will be added to the beginning
* of the list....
*
* @param root
* @return
*/
public List<Integer> postorder(Node root) {
LinkedList<Integer> list = new LinkedList<>();
if (root == null) {
return list;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node n = stack.pop();
//stack.addAll will make the right most child on top while is what we want
stack.addAll(n.children);
//add the newly processed val into the beginning of the list
list.addFirst(n.val);
}
return list;
}
/**
* regular approach, will visit each item twice. need to pop it only when its already been seen (i,e worked on its
* children)
*
* @param root
* @return
*/
public List<Integer> postorderUsingHash(Node root) {
Stack<Node> stack = new Stack<>();
stack.push(root);
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Set<Node> seen = new HashSet<>();
while (!stack.isEmpty()) {
Node n = stack.peek();
if (seen.contains(n)) {
stack.pop();
list.add(n.val);
} else {
//doing an inplace reversal, better to copy before changing order so that you
//dont modify the shape of the tree
Collections.reverse(n.children);
stack.addAll(n.children);
}
seen.add(n);
}
return list;
}
}