forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Inorder Traversal.java
More file actions
executable file
·215 lines (178 loc) · 5.04 KB
/
Binary Tree Inorder Traversal.java
File metadata and controls
executable file
·215 lines (178 loc) · 5.04 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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
E
1521646879
tags: Hash Table, Stack, Tree
Inorder traverse Binary Tree
#### Recursive
- 在自己的基础上recursive, 不用helper function
- Divide and Conquer, with helper(dfs) method
- O(n) time, no extra space
#### Iterative: Stack
- Add left nodes all the way
- Print curr
- Move to right, add right if possible
- O(n) time, O(h) space
注意stack.pop()在加完left-most child 的后，一定要curr = curr.right.
若不右移, 很可能发生窘境:
curr下一轮还是去找自己的left-most child，不断重复curr and curr.left, 会infinite loop, 永远在左边上下上下。
#### HashMap
? How?
```
/*
Given a binary tree, return the inorder traversal of its nodes' values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Challenge
Can you do it without recursion?
Tags Expand
Recursion Binary Tree Binary Tree Traversal
*/
/*
Thoughts:
Recursive, append left, itself, then right
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
if (root.left == null && root.right == null) {
rst.add(root.val);
return rst;
}
List<Integer> left = inorderTraversal(root.left);
List<Integer> right = inorderTraversal(root.right);
rst.addAll(left);
rst.add(root.val);
rst.addAll(right);
return rst;
}
}
/*
recap 3.15.2016
Recursive
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
dfs(rst, root);
return rst;
}
public void dfs(List<Integer> rst, TreeNode node) {
if (node.left != null) {
dfs(rst, node.left);
}
rst.add(node.val);
if (node.right != null) {
dfs(rst, node.right);
}
}
}
/*
Thoughts:
Iterative
Stack, always treat left-most-leaf with priority
- add node.left till end.
- consume stack.pop()
- if has right, add node.right and push all left children to stack
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> rst = new ArrayList<>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
// Dive deep to left-most leaf
while (node != null) {
stack.push(node);
node = node.left;
}
while (!stack.isEmpty()) {
// Add to rst
node = stack.pop();
rst.add(node.val);
// Add node.right and all left children
if (node.right != null) {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
return rst;
}
}
// Previous notes
/*
1. Use a helper method, recursively add to rst
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in ArrayList which contains node values.
*/
public ArrayList<Integer> inorderTraversal(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;
}
helper(rst, node.left);
rst.add(node.val);
helper(rst, node.right);
}
}
/*
2. Non-recursive
Inorder traversal: use 1 stack, push left till end; pirnt/store curr; push right to stack
'Curr' is always moving along with the curret position, representing the current node.
Note: after curr = curr.right, curr could be null; this will skip the while loop, and move on to next element.
Trick: in Inorder, we care the right node least. So we keep going with left and curr;
only when there is a right node, we add it;
even after this, we go deep into that right node's left children all the way down.
*/
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
stack.add(curr);
while (!stack.isEmpty()) {
while (curr != null && curr.left != null) {
stack.push(curr.left);
curr = curr.left;
}
//Pop the top node: the curr node
curr = stack.pop();
rst.add(curr.val);
//Move to right node, and push to stack if needed
curr = curr.right;
if (curr!= null) {
stack.push(curr);
}
}
return rst;
}
}
```