Leetcode--Java--199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

方法一：BFS

1. 层序遍历，每次存下每一层的最后一个，就是右视图。
2. 借助一个队列，注意是队列就不要使用push,pop这种方法，否则会当成栈。

方法二: DFS

1. 将DFS的访问顺序改为根结点->右子树->左子树。保证每次都是先访问右边的，这样最后就是右视图。
2. 注意可能会经过同一层很多次，但只用存下第一次访问的，所以设置一个depth变量记录当前深度，如果等于res说明结果集中该层还没有存储过，不等于说明已经存过了。

BFS：

class Solution {
    public List rightSideView(TreeNode root) {
       List res = new ArrayList<>();
       Deque stack = new ArrayDeque<>();
       if (root != null) {
           stack.push(root);
       }
       while (!stack.isEmpty()) {
           int size = stack.size();
           for (int i = 0; i < size; i ++ ) {
               TreeNode node = stack.poll();
               if (node.left != null) {
                   stack.offer(node.left);
               }
               if (node.right != null) {
                   stack.offer(node.right);
               }
               //到这层的最后一个，加入结果集
               if (i == size - 1) {
                   res.add(node.val);
               }
           }
       }
       return res;
    }
}

DFS：

class Solution {
    List res = new ArrayList<>();
    public List rightSideView(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        //看该层有没有存储过结点
        if (depth == res.size()) {
            res.add(root.val);
        }
        depth ++;
        //先遍历右子树，再遍历左子树
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}