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

方法一（递归+BFS）

1.题意整理

给定一颗二叉树的前序遍历序列和中序遍历序列。
打印出二叉树的右视图。

2.思路整理

重建二叉树：

一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到中序序列对应的头节点位置，则中序序列中该位置之前的一定是当前节点的左子树部分，该位置之后的一定是当前节点的右子树部分。知道了左右子树的节点个数，我们便可以推导出前序序列中左右子树的分界点。这样我们便可以构建当前节点的左右子树，通过递归的方式，便可以构建出树中每一个节点。

上面的思路中是通过遍历中序序列找到对应当前节点的位置，由于每次递归都需要搜索整个中序序列，时间复杂度较高，我们可以在递归之前对中序序列进行预处理，将中序序列的值与索引之间的映射加入到dic哈希表，然后递归的过程中直接从dic取出来即可。

递归终止条件：前序、中序中任意一个序列走完，递归就会终止。
递归如何传递：首先通过dic找到中序序列左右子树分界点，得到左右子树节点个数，进而可以推算出前序序列分界点。从而可以确定当前节点的左右子树。
递归的返回值：返回当前节点为根的子树。

层序遍历打印右视图： 重建二叉树之后，对二叉树进行层序遍历，建立一个临时list容器用于存储右视图，遍历二叉树的每一层，将每层最后一个元素加入list即可，最后将list容器转化为数组。

图解展示： alt

3.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    //存储中序序列中值和索引的映射
    Map<Integer,Integer> dic;
    public int[] solve (int[] xianxu, int[] zhongxu) {
        dic=new HashMap<>();
        //初始化
        for(int i=0;i<zhongxu.length;i++){
            dic.put(zhongxu[i],i);
        }
        
        //重建二叉树
        TreeNode root=createTree(xianxu,0,xianxu.length-1,zhongxu,0,zhongxu.length-1);
        //新建队列
        Queue<TreeNode> queue=new LinkedList<>();
        //加入根节点
        queue.offer(root);
        //存储右视图
        List<Integer> list=new ArrayList<>();
        while(!queue.isEmpty()){
            int n=queue.size();
            TreeNode node=null;
            //遍历当前层所有节点
            for(int i=0;i<n;i++){
                node=queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //将该层最后一个节点加入到list
            list.add(node.val);
        }
        //list集合转化为数组
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
        
    }
    
    //重建二叉树
    private TreeNode createTree(int[] xianxu,int l1,int r1, int[] zhongxu,int l2,int r2){
        //递归终止条件
        if(l1>r1||l2>r2) return null;
        //当前节点
        TreeNode root=new TreeNode(xianxu[l1]);
        //根据dic获取当前节点在中序序列中的位置
        int i=dic.get(xianxu[l1]);
        //重建当前节点的左子节点和右子节点
        root.left=createTree(xianxu,l1+1,l1+i-l2,zhongxu,l2,i-1);
        root.right=createTree(xianxu,l1+i-l2+1,r1,zhongxu,i+1,r2);
        return root;
    }
}

4.复杂度分析

时间复杂度：重建二叉树时，需要重建所有的节点，时间复杂度为 $O (n)$ ，寻找右视图时，也需要遍历所有的节点，每个节点进队和出队一次，时间复杂度为 $O (n)$ ，所以最终的时间复杂度为 $O (n)$ 。
空间复杂度：最坏情况下，递归栈深度为n，队列大小不超过n，所以空间复杂度是 $O (n)$ 。