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 <---
题意：
给定一个二叉树，
想象自己站在二叉树的右侧
返回所有能看到的node(返回的node的order是从上往下)
思路：
dfs，
使其访问顺序为： root --> right --> left
这样访问nodes为：10, 15, 20, 12, 5, 7, 9, 2
用一个level来维护每层关系, 便于把每层最右侧nodes取出来，放入result中
则：（10,0), (15,1), (20,2), (12,2), (5,1), (7,2), (9,3), (2,2)
每次一到达新的level，根据root --> right --> left的访问顺序，该新level最先被访问的node一定是最右侧view 需要输出的node。将其加入result中。
（10,0), (15,1), (20,2), (12,2), (5,1), (7,2), (9,3), (2,2)
result输出： 10， 15， 20， 9
代码：
public class BinaryTreeRightSideView {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// corner case
if (root == null) return result;
dfs(root, result, 0);
return result;
}
public void dfs(TreeNode root, List<Integer> result, int level) {
//recursion 的base case
if (root == null) {
return;
}
if (level == result.size()) {
result.add(root.val);
}
dfs(root.right, result, level + 1);
dfs(root.left, result, level + 1);
}
}思路
BFS（iteration）
每次先将right side node 加入到queue里去
保证 当i = 0 的时候，poll出来的第一个item是right side node
代码
1 public List<Integer> rightSideView(TreeNode root) {
2 // level order traversal
3 List<Integer> result = new ArrayList();
4 Queue<TreeNode> queue = new LinkedList();
5 // corner case
6 if (root == null) return result;
7
8 queue.offer(root);
9 while (!queue.isEmpty()) {
10 int size = queue.size();
11 for (int i = 0; i< size; i++) {
12 TreeNode cur = queue.poll();
13 // make sure only add right side node
14 if (i == 0) result.add(cur.val);
15 // add right side node first, making sure poll out first
16 if (cur.right != null) queue.offer(cur.right);
17 if (cur.left != null) queue.offer(cur.left);
18 }
19 }
20 return result;
21 }