-
Notifications
You must be signed in to change notification settings - Fork 9
/
Binary Tree Postorder Traversal (pyemma)
53 lines (49 loc) · 1.42 KB
/
Binary Tree Postorder Traversal (pyemma)
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
import java.util.*;
public class BinaryTreePostorderTraversal {
ArrayList<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<Integer>();
TreeNode dump = new TreeNode(0);
dump.left = root; dump.right = null;
TreeNode cur = dump, tmp;
while(cur != null) {
if(cur.left == null) {
cur = cur.right;
}
else {
tmp = cur.left;
while(tmp.right != null && tmp.right != cur) tmp = tmp.right;
if(tmp.right == null) {
tmp.right = cur;
cur = cur.left;
}
else {
addReverse(cur.left, tmp);
tmp.right = null;
cur = cur.right;
}
}
}
return res;
}
private void reverse(TreeNode from, TreeNode to) {
if(from == to) return;
TreeNode x = from, y = from.right, z;
while(x != to) {
z = y.right;
y.right = x;
x = y;
y = z;
}
}
private void addReverse(TreeNode from, TreeNode to) {
reverse(from, to);
TreeNode t = to;
while(true) {
res.add(to.val);
if(to == from) break;
to = to.right;
}
reverse(to, from);
}
}