题目：
199. Binary Tree Right Side View(medium)
解题思路：
分为BFS解法和DFS解法
BFS中取每层最后一个节点进结果集中；
DFS先访问根节点，再先向右走，再向左走，每次进第一个访问到的节点
代码：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
38BFS:
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Deque<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int sz = q.size();
for(int i = 0;i < sz;i++){
TreeNode node = q.poll();
if(node.left != null) q.offer(node.left);
if(node.right != null) q.offer(node.right);
if(i == sz - 1) res.add(node.val);
}
}
return res;
}
DFS:
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root,0);
return res;
}
private void dfs(TreeNode root,int depth){
if(root == null) return ;
//先访问当前结点，再访问 右子树 和 左子树
//如果当前结点所在深度 等于 结果集的长度，则证明当前节点是最右边的节点，即第一个杯访问的节点，要加入res中
if(depth == res.size())
res.add(root.val);
depth ++;
dfs(root.right,depth);
dfs(root.left,depth);//这句不能省，因为有只有左子树没有右子树的情况，这时要返回左子树的节点
}
