1 题目描述

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

2 解题思路

此题是二叉树层序遍历的拓展。

1. 创建一个队列que (Queue)起到中介的作用，对其进行操作获得目标元素；创建一个res (ArrayList)存放目标元素。
2. 根节点进入队列que中, 进入条件为队列que非空的循环中，记录此时que的大小len。
3. 再嵌套一个条件为len>0的循环，循环体为队列que弹出队首元素，当len=1时，弹出的队首元素即为目标元素之一，保存在res中，然后len-1，弹出队首元素的同时，若存在则将队首元素的左右节点加入到队列中。
4. 返回目标res

3 流程图

3 代码

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res =new ArrayList<>( );
        if (root == null) return res;

        Queue<TreeNode> que = new LinkedList<>( );
        que.offer( root );

        while ( ! que.isEmpty( ) ){
            int len = que.size( );
            while ( len>0 ){
                TreeNode node = que.poll( );
                if (len == 1) res.add( node.val );
                if (node.left != null) que.offer( node.left );
                if (node.right != null) que.offer( node.right );
                len--;
            }
        }

        return res;
    }