-
Notifications
You must be signed in to change notification settings - Fork 0
/
BTRightView.java
62 lines (54 loc) · 1.68 KB
/
BTRightView.java
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
/*
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.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
Analysis:
1. BFS, triverse tree level by level, always return right most node of each level.
2. Recursive,
Each depth of the tree only select one node.
View depth is current size of result list.
*/
class BTRightView
{
//Method 1: iterate
public List<Integer> rightSideView(TreeNode root)
{
List<Integer> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
if (root == null) return result;
queue.offer(root);
while (queue.size() != 0) {
int size = queue.size();
for (int i=0; i<size; i++) {
TreeNode cur = queue.poll();
if (i == 0) result.add(cur.val);
if (cur.right != null) queue.offer(cur.right);
if (cur.left != null) queue.offer(cur.left);
}
}
return result;
}
//Method 2: recursive
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public void rightView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}
rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);
}
}