给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
解题思路
树的遍历，题目要求返回树最又层的那一列，首先想到的是DFS和BFS，因为不知道每个分支的深度，所以在DFS深度遍历时，要记得当前深度有没有记录过最右边的节点，同理在BFS宽度遍历时，也要确保最右侧的节点被记录过。
DFS解法
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
int depth = 0;
dfs(list,root,depth);
return list;
}
private void dfs(List<Integer> list,TreeNode root,int depth)
{
if(root != null)
{
if(depth == list.size())
{
list.add(root.val);
}
depth++;
dfs(list,root.right,depth);//优先访问右侧节点
dfs(list,root.left,depth);
}
}
}
BFS解法
class Solution {
public List<Integer> rightSideView(TreeNode root){
List<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null) return list;
queue.offer(root);
while(!queue.isEmpty())
{
//获取一层中最右边的那个节点
int size = queue.size(); //提前算出来大小，因为大小时刻在变
for(int i=0;i<size;i++)
{
TreeNode node = queue.poll();
if(i == size -1)
{
if(node != null) list.add(node.val);
}
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
return list;
}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
