题解 | 输出二叉树的右视图

解题思路：本题是二叉树集合学习的集成检验。解题思路可以主要分为三步。

1. 二叉树恢复：从已知前序、中序中恢复二叉树。
2. 记录左视图：即获取二叉树中每一层最右边的节点。
3. 考虑是否存在边界情况：空树 --> 返回空；一个节点 --> 返回该节点。

代码实现思路：

恢复二叉树（辅助函数：buildTree）：从前序遍历（preOrder）中获取根节点，从中序遍历（inOrder）中的根节点将数组分为左子树和右子树。从而构建左子树和右子树。因此在递归构建时，最重要的是对中序遍历数据进行正确分割，并传递每一次递归时划分的索引开始值与索引结束值。

在中序数组中，根节点的索引为inRoot，inStart为中序数组的起始位置，inEnd为中序数组的结束位置。所以左子树对应索引为：inStart -- inRoot -1，左子树长度为：inRoot - inStart。右子树对应索引为：inRoot+1 -- inEnd，右子树的长度为：inEnd - inRoot。

因此可以，可以通过在每次递归调用时，传入前序和中序数组，以及当前子树在前序中的起始位置和长度，或者索引范围来处理。

其次，在之前的重建二叉树题目中，是通过不断复制数组进行递归的。因此可以用一个哈希表HashMap预先将中序元素与其索引进行记录，通过递归索引值直接寻址，提高效率。

获取右视图（BFS层次遍历，辅助函数：rightSideView）：初始化一个队列，加入根节点。然后循环处理每一层。对于每一层，记录该层的节点数，然后取出当前层的所有节点，将它们的子节点加入队列。每层的最后一个节点就是右视图的元素。将最后一个节点的值加入结果列表。

当队列不为空时：记录当前层的节点数 size = queue.size()

遍历size次，取出节点

如果时当前层的最后一个节点（i == size -1），将值加入结果列表。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        //解题思路：
        //第一步：从前序和中序中恢复二叉树：从前序中获取根节点，然后在中序中找到根节点的位置，左边即为左子树的中序遍历结果，右边即为右子树的中序遍历结果。同理，递归进行区分。
        //第二步：右视图即为每一层右边的节点。可以用层序遍历法（BFS），记录每层最后一个节点的值。或者用深度遍历法（DFS），优先右子树，左子树，如果当前深度还没有记录过节点，就保存当前结点值。
        //第三步：考虑一些边界情况：空树 --> 返回空；一个节点 --> 返回自己

        //代码实现：
        if(preOrder == null || inOrder == null || preOrder.length != inOrder.length ){
            return null;
        }

        Map<Integer,Integer> inMap = new HashMap<Integer,Integer>();
        //遍历将中序中的 索引 与 值 一一对应放入HashMap中，便于寻址。
        for(int i = 0; i< inOrder.length;i++){
            inMap.put(inOrder[i],i);
        }

        TreeNode root = buildTree(preOrder, 0 , preOrder.length-1, inOrder, 0 , inOrder.length -1, inMap);
        List<Integer> result = rightSideView(root);
        int[] r1 = new int[result.size()];
        for(int i =0;i<result.size();i++){
            r1[i] = result.get(i);
        }

        return r1;
    }

    //定义辅助函数：恢复二叉树
    private TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd, Map<Integer,Integer> inMap){
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        //创建根节点，从前序中取出值
        TreeNode root = new TreeNode(preOrder[preStart]);
        //在记录了中序索引与对应值的HashMap中，直接获取根节点的索引值。
        int inRoot = inMap.get(root.val);
        //获取左子树的节点数量
        int leftSize = inRoot - inStart;

        root.left = buildTree(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, inRoot -1, inMap);

        root.right = buildTree(preOrder, preStart + leftSize +1, preEnd, inOrder, inRoot +1, inEnd, inMap);

        return root;

    }


    //定义函数：BFS记录右视图节点
    private List<Integer> rightSideView(TreeNode root){
        //层序遍历BFS，记录每层最后一个节点
        if(root == null){
            return null;
        }

        List<Integer> result = new ArrayList<Integer>();
        //创建队列，用于遍历BFS
        Queue<TreeNode> q = new LinkedList<TreeNode>();

        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i =0;i<size;i++){
                TreeNode node = q.poll();
                if(i == size -1){
                    result.add(node.val);
                }

                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
        }

        return result;
    }

}