力扣---199. 二叉树的右视图-526互联

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

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

深度优先遍历或广度优先遍历。

深度优先遍历的话，用一个变量来记录深度。

先遍历右节点。

这样可以保证先看到的是最右边的节点。

遇到新的深度，则意味着该节点是该深度最靠右的节点。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list, 0);
        return list;
    }
    private void dfs(TreeNode node, List<Integer> list, int count) {
        if (node == null) {
            return;
        }
        if (count >= list.size()) {
            list.add(node.val);
        }
        dfs(node.right, list, count + 1);
        dfs(node.left, list, count + 1);
    }
}

深度优先遍历的话，需要处理完某一层的最后一个节点的值放到 list 中。

class Solution {
    public List<Integer> rightSideView (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            // 记录当前层次的数量。
            int len = deque.size();
            // 最右边，直接用 getLasst 方法即可。
            list.add(deque.getLast().val);
            // 将下一层的节点添加到 deque 中。
            for (int i = 0; i < len; i ++) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
        }
        return list;
    }
}