forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Postorder Traversal.java
More file actions
executable file
·137 lines (115 loc) · 3.11 KB
/
Binary Tree Postorder Traversal.java
File metadata and controls
executable file
·137 lines (115 loc) · 3.11 KB
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
E
最prefer 2 stack的做法：
stack1和stack2合作。倒水。记这个做法。。。挺神奇的。
Divide and Conquer 的recursive方法也非常明了！
注意，这些binary tree traversal的题目，常常有多个做法:recursive or iterative
```
/*
Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Challenge
Can you do it without recursion?
Tags Expand
Binary Tree
*/
/*
Thinking process:
1. Resursive: （divide and conquer）
rec on left node
rec on right node
rst.addAll(left)
rst.addAll(right)
rst.add(curr)
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in ArrayList which contains node values.
*/
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
//Recursive:
ArrayList<Integer> right = postorderTraversal(root.right);
ArrayList<Integer> left = postorderTraversal(root.left);
rst.addAll(left);
rst.addAll(right);
rst.add(root.val);
return rst;
}
}
/*
2. Non-recursive, iterative
use 2 stacks: pull water from s1 into s2
in s2, we want: at each level, parentNode at bottom, then rightNode, then leftNode
loop through s2, then we print out leftNode, rightNode, parentNode ... in postOrder.
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in ArrayList which contains node values.
*/
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
//Non-recursive:
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
s1.push(root);
while (!s1.empty()) {
TreeNode curr = s1.pop();
s2.push(curr);
if (curr.left != null) {
s1.push(curr.left);
}
if (curr.right != null) {
s1.push(curr.right);
}
}
while (!s2.empty()) {
rst.add(s2.pop().val);
}
return rst;
}
}
/*
Recap 12.08.2015
Besides the 2 old ways of doing it, we can:
3. Recursive with helper method.
*/
//Recursive with helper
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
helper(rst, root);
return rst;
}
public void helper(ArrayList<Integer>rst, TreeNode node) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
rst.add(node.val);
return;
}
helper(node.left);
helper(node.right);
rst.add(node.val);
}
}
```