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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    static Map<Integer,Integer> indexForInOrders=new HashMap<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
         for (int i = 0; i < zhongxu.length; i++){
            indexForInOrders.put(zhongxu[i], i);
         }
         List<Integer> lists=rightView(dfs(xianxu,0,xianxu.length-1,0));
         int[] result=new int[lists.size()];
         int len=lists.size();
         for(int i=0;i<len;i++){
             result[i]=lists.get(i);
         }
         return result;
    }
    public TreeNode dfs(int[] pre, int preL, int preR, int inL){
        if(preL>preR){
            return null;
        }
        TreeNode root=new TreeNode(pre[preL]);
        int indexZhong=indexForInOrders.get(pre[preL]);
         int leftTreeSize = indexZhong - inL;
        root.left=dfs(pre,preL+1,preL+leftTreeSize,inL);
        root.right=dfs(pre,preL+leftTreeSize+1,preR,inL+leftTreeSize+1);
        return root;
    }
    public List<Integer> rightView(TreeNode root){
        List<Integer> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            while(size>0){
                TreeNode node=queue.poll();
                if(size==1){
                    ret.add(node.val);
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                size--;
            }
        }
        return ret;
    }
}