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
·163 lines (135 loc) · 4.1 KB
/
Binary Tree Postorder Traversal.java
File metadata and controls
executable file
·163 lines (135 loc) · 4.1 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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
M
1521692416
tags: Stack, Two Stacks, Tree
如题, POST-ORDER traversal.
LeetCode给了hard, 应该是觉得stack的做法比较难想到.
#### Recursive
trivial, 先加left recursively, 再加right recursively, 然后组成头部.
#### Stack
- 双stack的思想, 需要在图纸上画一画
- 原本需要的顺序是: 先leftChild, rightChild, currNode.
- 营造一个stack, reversely process: 先currNode, 再rightChild, 再leftChild
- 这样出来的结果是reverse的, 那么翻转一下就可以了.
- v1做的时候用了stack1, stack2, 因为根据这个双stack的思想而来
- v2简化, 可以放在一个stack里面, 每次record result 的时候: rst.add(0, item);
##### 利用stack的特点
- 每次加element进stack的时候, 想要在 bottom/后process的, 先加
- 想要下一轮立刻process的, 最后push进stack.
##### 注意
这些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
*/
// Recursive: always add left, add right, then add middle
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
rst.addAll(postorderTraversal(root.left));
rst.addAll(postorderTraversal(root.right));
rst.add(root.val);
return rst;
}
}
/*
Iteratively: stack
V1
it's cleaner to draw two stacks and simulate the add proces on paper
- stack2 is a placeholder with reversed post-order. It'll be used to generate final results.
- Item in stack1 will be added with reversed order: left, right
- Always save the parent node to stack2: it enters stack2 first than its 2 children, so it'll be at bottom
- Next round: since right child is on top, it'll be processed first and added to stack2
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
rst.add(stack2.pop().val);
}
return rst;
}
}
// Simpler version, add to begining of list.
// V2
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
rst.add(0, node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
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);
}
}
```