[[LeetCode]46. 二叉树的右侧视图、左侧视图

🚩传送门：题目

题目

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

示例 1:

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

示例 2:

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

示例 3:

输入: [] 输出: []

解题思路：BFS

• 创建队列 queue，当 root 不为空时，将 root 加入队列，然后开始 while 循环
• 每次 while 循环记录下 queue 的长度，这是本一层的所有元素个数
• 将元素入队的时候，先右后左，那么每一层的开始的第一个就是最后边的元素

  - **同理：**先左后右，那么每一层的开始的第一个就是最左边的元素

官方代码 [右视图]

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        //1. 队列
        Queue<TreeNode> queue=new LinkedList<>();
        //2. 结果集
        List<Integer> res=new LinkedList<>();
        if(root==null)return res;
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            //3. 队列的循环开始的第一个一定是最右边的结点
            res.add(queue.peek().val);
            //4. 通过size控制每一层循环的个数
            for(int i=0;i<size;i++){
                //5. 先右后左,每一层的第一个结点一定是最右边结点
                if(queue.peek().right!=null)
                    queue.add(queue.peek().right);
                if(queue.peek().left!=null)
                    queue.add(queue.peek().left);
                queue.poll();
            }
        }
        return res;
    }
}

官方代码 [左视图]

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> res=new LinkedList<>();
        if(root==null)return res;
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            res.add(queue.peek().val);
            for(int i=0;i<size;i++){
                //先左后右,每一层的第一个结点一定是最右边结点
                if(queue.peek().left!=null)
                    queue.add(queue.peek().left);
                if(queue.peek().right!=null)
                    queue.add(queue.peek().right);
                queue.poll();
            }
        }
        return res;
    }
}