LeetCode-199-二叉树的右视图

题目

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

示例 1:

img

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

示例 2:

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

示例 3:

输入: []
输出: []

提示:

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

题解

这一题其实就是求解层序遍历的时候，每一层的最后一个节点，那么就很简单了：

正常的层序遍历方法，我们将每一层的节点放在一个队列queue中；

但是这里我们做一个特殊的处理，就是往队列里存的时候，我们先存右边的，再存左边的，这样队列里的第一个数据就是所求的数据了，方便我们进行获取；

然后把对应的数据放在list里返回就好啦。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 层序遍历每层最后的节点
        List<Integer> res = new ArrayList<>();
        bfs(root, res);
        return res;
    }

    public void bfs(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            // 将数据放到list里
            res.add(queue.peek().val);
            while (size > 0) {
                // 先储存right这样第一个就是所求的数据
                TreeNode temp = queue.poll();
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                size--;
            }
        }
    }
}