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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
       public static int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        List<Integer> list1=new ArrayList<Integer>();
        List<Integer> list2=new ArrayList<Integer>();//存储深度同一层的最右侧节点的值
        dfs(xianxu,zhongxu,0,xianxu.length-1,0,zhongxu.length-1,list1,list2,0,1);
        int[] rst=list2.stream().mapToInt(Integer::intValue).toArray();
        return rst;
    }
    public static void dfs(int[] preorder,int[] inorder,int prel,int prer,int inl,int inr,List<Integer> list1,List<Integer> list2,int order,int level){
        if(prel>prer||inl>inr){
            return;
        }
        int num=preorder[prel];
        int index=inl;
        while(inorder[index]!=num&&index<=inr){
            index++;
        }
        if(list2.size()<level){
            list2.add(num);
            list1.add(order);
        }else if(list1.get(level-1)<order){
            list2.set(level-1,num);
            list1.set(level-1,order);
        }
        //list2.set(level-1, num);
        int leftLength=index-inl;
        int rightLength=inr-index;
        dfs(preorder,inorder,prel+1,prel+leftLength,inl,index-1,list1,list2,2*order+1,level+1);
        dfs(preorder,inorder,prel+leftLength+1,prer,index+1,inr,list1,list2,2*order+2,level+1);
    } 
}