forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Right Side View.java
More file actions
executable file
·217 lines (179 loc) · 5.39 KB
/
Binary Tree Right Side View.java
File metadata and controls
executable file
·217 lines (179 loc) · 5.39 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
216
217
M
1526769889
tags: Tree, DFS, BFS
给一个binary tree, 从右边看过来, return all visible nodes
#### BFS
- 最右:即level traversal每一行的最末尾.
- BFS, queue 来存每一行的内容, save end node into list
#### DFS
- Use Map<Level, Integer> 来存每一个level的结果
- dfs function 里, 如果 input depth 不存在, 就add to map.
- dfs function 里面先: dfs(node.right), 然后 dfs(node.left)
- 由于always depth search on right side, 所以map会被right branch populate; 然后才是 leftChild.right
```
/*
Given a binary tree, imagine yourself standing on the right side of it,
return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
1 <---
/ \
2 3 <---
\ \
5 4 <---
*/
/*
right side view:
- the tree may not be complete
- always find right-most. if right child not available, dfs into left child
- tracking back is hard for dfs
- bfs: on each level, record the last item of the queue
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// check edge case
if (root == null) {
return result;
}
// init queue, result list
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// loop over queue with while loop; inner while loop to complete level
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
size--;
TreeNode node = queue.poll();
if (size == 0) {
result.add(node.val);
}
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
return result;
}
}
/*
DFS: mark each level with map<level, node>
1. dfs right side first, then left side at each level
2. if candidate not exist, add to map, if exist, skip.
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// check edge case
if (root == null) {
return result;
}
// init map, dfs
Map<Integer, Integer> map = new HashMap<>();
int depth = dfs(map, root, 0);
// output result
for (int i = 0; i <= depth; i++) {
if (map.containsKey(i))
result.add(map.get(i));
}
return result;
}
private int dfs(Map<Integer, Integer> map, TreeNode node, int depth) {
if(node == null) {
return 0;
}
if (!map.containsKey(depth)) {
map.put(depth, node.val);
}
int rightDepth = dfs(map, node.right, depth + 1);
int leftDepth = dfs(map, node.left, depth + 1);
return Math.max(leftDepth, rightDepth) + depth;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
02.09.2016 Revist
Thoughts:
BFS: traverse all levels, save to ArrayList, get all nodes at end of level list.
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int size = queue.size();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
size--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (size == 0) {
rst.add(node.val);
size = queue.size();
}
}
return rst;
}
}
/*
自己想了这个方法，有可能不是特别efficient.
一个queue放普通的BFS。
一个queue放level。
同时维护一个parent value；维护一个跟着BFS跑的level。
每个node都有一个lv。一旦lv和正在跑的level不一样，证明lv>level，那么也就是说，刚刚换行拉。parent的值，就是上一行最右边的值。DONE.
Thoughts:
Use 2 queue: one for BFS, one for level. Each node in queue has a corresponding level
Track level.
WHen level != levelQ.poll(), that means we are moving to next level, and we should record the previous(parent) node's value.
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> rst = new ArrayList<Integer>();
if (root == null) {
return rst;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
Queue<Integer> levelQ = new LinkedList<Integer>();
q.offer(root);
levelQ.offer(1);
int level = 1;
int parent = root.val;
TreeNode node = null;
while (!q.isEmpty()) {
node = q.poll();
int lv = levelQ.poll();
if (level != lv) {
level++;
rst.add(parent);
}
parent = node.val;
if (node.left != null) {
q.offer(node.left);
levelQ.offer(lv + 1);
}
if (node.right != null) {
q.offer(node.right);
levelQ.offer(lv + 1);
}
}//END while
rst.add(parent);
return rst;
}
}
```