[数据结构与算法]（LeetCode）二叉树的右视图

给定一个二叉树的 根节点 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?

第一次写的时候，考虑简单了，认为既然是右视图，那么看到的节点肯定是所有的右节点的右节点

如：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> it = new ArrayList<>();
        TreeNode head = root;
        if  (root == null) return it;
        while(head != null){
            it.add(head.val);
            head = head.right;
        }
        return it;

    }
}

执行代码的时候还没有错，直到提交的时候才发现，是我想简单了。

这个题目想找的是每一层最右边的那个节点，因为可以用树的层次遍历进行解决

层次遍历：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> it = new ArrayList<>();
        if  (root == null) {
            return it;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (! queue.isEmpty()){
            int count = queue.size();//用来记录每层的节点数
            while (count > 0){
                TreeNode cur = queue.poll();
                count--;
                if (count == 0){
                    it.add(cur.val);
                }
                if (cur.left != null){
                    queue.add(cur.left);
                    
                }
                if (cur.right != null){
                    queue.add(cur.right);
                    
                }
            }
        }

        return it;
    

思路是用队列存储每层的节点，每次存完一层的节点之后都获取每层的节点数，然后依据节点数来判断节点是否为每层最后一个节点，如果是最后一个节点就将节点的值存入列表

第二种方法是用递归，：思路分别定义一个树的层数和列表的长度，如果一个节点（优先右节点）的层数和当时的列表长度相同则认为这个节点的值可以存入列表。

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> it = new ArrayList<>();
        getRightNode(root,it,0);//初始层数为0
        return it;

    }

    private void getRightNode(TreeNode root,List<Integer> it,int depth){
        if (root == null) {
            return;
        }
        if (it.size() == depth){
            it.add(root.val);
        }
        getRightNode(root.right,it,depth+1);//优先右节点
        getRightNode(root.left,it,depth+1);
    }