输出二叉树的右视图

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        List<Integer> result = new ArrayList<>();
        if (preOrder.length < 1 || preOrder.length != inOrder.length) {
            return null;
        }
        // 根据前序遍历和中序遍历构造二叉树
        TreeNode root = buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
        if (root == null) {
            return null;
        }
        // 使用迭代法寻找二叉树的最右侧节点
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            // 求出每层节点的数量
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.removeFirst();
                // size - 1即为最右侧节点，加入到result结果列表中
                if (i == size - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
        }
        return result.stream().mapToInt(x -> x).toArray();
    }

    // 根据前序遍历和中序遍历构造二叉树
    public TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int root_val = preOrder[preStart];
        TreeNode root = new TreeNode(root_val);
        int index = 0;
        for (index = 0; index < inOrder.length; index++) {
            if (inOrder[index] == root_val) {
                break;
            }
        }
        int left_length = index - inStart;
        root.left = buildTree(preOrder, preStart + 1, preStart + left_length, inOrder, inStart, index - 1);
        root.right = buildTree(preOrder, preStart + left_length + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    int index=0;
    ArrayList<Integer> result=new ArrayList<>();
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        int deep=0;
        ArrayList<Integer>list=new ArrayList<>();
        for(int i=0;i<inOrder.length;i++){
            list.add(inOrder[i]);
        }
        a(list,preOrder,0,result);
        int[] r=new int[result.size()];
        for(int i=0;i<r.length;i++){
            r[i]=result.get(i);
        }
        return r;
    }
    public void a( ArrayList<Integer>list,int[] preOrder,int deep,ArrayList<Integer>result){
        if(list.size()<=0||index==preOrder.length)return;
        if(deep>=result.size())
            result.add(preOrder[index]);
        else
            result.set(deep,preOrder[index]);
        int flag=0;
        ArrayList<Integer>left=new ArrayList<>();
        ArrayList<Integer>right=new ArrayList<>();
        for(int b:list){
            if(b==preOrder[index]){
                flag=1;
                continue;
            }
            if(flag==0)
                left.add(b);
            else
                right.add(b);
        }
        index++;
        a(left,preOrder,deep+1,result);
        a(right,preOrder,deep+1,result);
    }
}

import java.util.*;


public class Solution {
    // 将哈希表创建在成员变量的位置,这样就不用在参数中传递了
    private HashMap<Integer,Integer> map = new HashMap<>();

    // 根据前序遍历和中序遍历构建二叉树
    private TreeNode buildTree(int[] preOrder, int[] inOrder) {
        // 1. 将中序遍历的结果放到哈希表中
        for(int i = 0;i < inOrder.length;i++) {
            map.put(inOrder[i],i);
        }

        // 2. 调用具体的构造二叉树的方法
        return process(preOrder,0,preOrder.length - 1,inOrder,0,inOrder.length - 1);
    }

    // 构造二叉树
    private TreeNode process(int[] preOrder,int l1,int r1,int[] inOrder,int l2,int r2) {
        // 1. 递归退出条件
        if(l1 > r1) {
            return null;
        }

        // 2. 构造根节点
        TreeNode root = new TreeNode(preOrder[l1]);

        // 3. 找出中序遍历根节点的位置
        int find = map.get(preOrder[l1]);

        // 4. 左右递归连接根节点
        root.left = process(preOrder,l1 + 1,l1 + find - l2,inOrder,l2,find - 1);
        root.right = process(preOrder,l1 + find - l2 + 1,r1,inOrder,find + 1,r2);

        // 5. 返回根节点
        return root;
    }

    public int[] solve (int[] preOrder, int[] inOrder) {
        // 1. 参数校验
        if(preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return null;
        }

        // 2. 创建出二叉树
        TreeNode root = buildTree(preOrder,inOrder);

        // 3. 创建辅助队列
        Queue<TreeNode> queue = new LinkedList<>();

        // 4. 创建答案数组
        ArrayList<Integer> result = new ArrayList<>();

        // 5. 将根节点加入到队列中
        if(root != null) {
            queue.offer(root);
        }

        // 6. 队列不为空,弹出队列的元素,判断他有没有左右子树,有的话加入到队列中
        while(!queue.isEmpty()) {
            // 7. 获取当前队列的元素个数(当层的元素个数)
            int size = queue.size();

            // 8. 创建 ret 表示该层最后一个元素
            int ret = 0;

            // 9. 遍历 size 个节点
            while(size-- != 0) {
                // 10. 弹出队首元素
                TreeNode cur = queue.poll();

                // 11. 更新 ret 
                ret = cur.val;

                // 12. 判断是否有左右子树
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }

            // 13. ret 保存了该层最后一个节点的值
            result.add(ret);
        }

        // 14. 将顺序表转化层数组返回
        int[] ans = new int[result.size()];
        for(int i = 0;i < result.size();i++) {
            ans[i] = result.get(i);
        }
        return ans;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] pre, int[] in) {
        // write code here
        //拿到根节点，层序遍历，每次遍历到每层的最后一个结点加入到ArrayList中
        TreeNode root = solveRoot(pre , in) , temp;
        ArrayList<Integer> arr = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()){
            int k = q.size();
            for (int i = 0; i < k; i++) {
                temp = q.poll();
                if(i == k - 1){
                    arr.add(temp.val);
                }
                if(temp.left != null)
                    q.add(temp.left);
                if(temp.right != null)
                    q.add(temp.right);
            }
        }
        int[] res = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            res[i] = arr.get(i);
        }
        return res;
    }

    //复原树返回根节点
    public TreeNode solveRoot(int[] pre , int[] in){
        int n = pre.length;
        int m = in.length;
        if(n == 0 || m == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < m; i++) {
            if(pre[0] == in[i]){
                node.left = solveRoot(Arrays.copyOfRange(pre , 1 , i + 1) , Arrays.copyOfRange(in , 0 , i));
                node.right = solveRoot(Arrays.copyOfRange(pre , i + 1 , n) , Arrays.copyOfRange(in , i + 1 , m));
                break;
            }
        }
        return node;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    Map<Integer,Integer> map=new HashMap<>();
    public int[] solve (int[] preOrder, int[] inOrder) {
        for(int i=0;i<inOrder.length;i++){
            map.put(inOrder[i],i);
        }
        TreeNode root=build(preOrder,0,preOrder.length,inOrder,0,inOrder.length);
        //层序遍历
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            int level=qu.size();
            ArrayList<Integer> levelList=new ArrayList<>();
            for(int i=0;i<level;i++){
                TreeNode peek=qu.peekFirst();
                levelList.add(qu.pollFirst().val);
                if(peek.left!=null) qu.offerLast(peek.left);
                if(peek.right!=null) qu.offerLast(peek.right);
                if(i==level-1){//当遍历到了最后一层，才加入ans
                    list.add(peek.val);
                }
            }
        }
        int[] ans=new int[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }
    public TreeNode build(int[] preOrder,int preBegin,int preEnd,int[] inOrder,int inBegin,int inEnd){
        if(preBegin>=preEnd||inBegin>=inEnd){
            return null;
        }
        int rootIndex=map.get(preOrder[preBegin]);
        TreeNode root=new TreeNode(preOrder[preBegin]);
        int leftValue=rootIndex-inBegin;

        root.left=build(preOrder,preBegin+1,preBegin+1+leftValue,inOrder,inBegin,rootIndex);
        root.right=build(preOrder,preBegin+1+leftValue,preEnd,inOrder,rootIndex+1,inEnd);
        return root;

    }

import java.util.*;


public class Solution {

    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        //先序
        List<Integer> preList=new ArrayList<>();
        //中序
        List<Integer> midList=new ArrayList<>();
        for(int i=0;i<xianxu.length;i++){
            preList.add(xianxu[i]);
            midList.add(zhongxu[i]);
        }
        //构建树
        TreeNode root=getTree(preList,midList);
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> getResult=new ArrayList<>();
        //层序遍历获取最右边的值
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(i==size-1){
                    getResult.add(node.val);
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        //将结果输出到数组
        int arr[]=new int[getResult.size()];
        for(int i=0;i<getResult.size();i++){
            arr[i]=getResult.get(i);
        }
        return arr;
    }
    //构造树
    public TreeNode getTree(List<Integer> preList,List<Integer> midList){
        if(midList.isEmpty()){
            return null;
        }
        int rootVal=preList.remove(0);
        TreeNode root=new TreeNode(rootVal);
        int mid=midList.indexOf(rootVal);
        root.left=getTree(preList,midList.subList(0,mid));
        root.right=getTree(preList,midList.subList(mid+1,midList.size()));
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root =  dfs(0, 0, zhongxu.length - 1, xianxu,zhongxu);
        return TreerightView(root);
    }

    private int[] TreerightView(TreeNode root){
        if(root==null){
            return new int[0];
        }
        Queue<TreeNode> qu = new LinkedList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        qu.add(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i=0;i<size;i++){
                TreeNode cur = qu.poll();
                if(i==size-1) arr.add(cur.val);
                if(cur.left!=null) qu.add(cur.left);
                if(cur.right!=null) qu.add(cur.right);
            }
        }
        // //将ArrayList转为int[]
        // int arrsize = arr.size();
        // int[] arrint = new int[arrsize];
        // for(int i=0;i<arrsize;i++){
        //     arrint[i]=arr.get(i).intValue();
        // }
        // return arrint;

        return arr.stream().mapToInt(Integer::intValue).toArray();

    }

    private TreeNode dfs(int preStart, int vinStart, int vinEnd, 
    int[] preOrder,int[] vinOrder) {
        //元素为空//位置不对
        if (preStart > preOrder.length - 1 || vinStart > vinEnd) {
            return null;
        }
        //从先序遍历首元素构建结点
        TreeNode root = new TreeNode(preOrder[preStart]);
        int index = 0;
        //查找中序遍历结果位置
        for (int i = vinStart; i <= vinEnd; i++ ) {
            if (vinOrder[i] == root.val) {
                index = i;
                break;
            }
        }
        //左结点为先序下一个结点,且该节点位于index左侧
        root.left = dfs(preStart + 1, vinStart, index - 1, preOrder, vinOrder);
        //右结点先序位置为当前结点先序位置+(当前结点左子树数量(当前中序位置-中序开始位置)+当前结点)
        root.right = dfs(preStart + index - vinStart + 1, index + 1, vinEnd, preOrder,vinOrder);
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = build(xianxu, 0, xianxu.length - 1, zhongxu, 0,
                              zhongxu.length - 1);
        //找到右视图
        LinkedList<TreeNode> qu = new LinkedList<TreeNode>();
        qu.add(root);
        List<Integer> list = new ArrayList<Integer>();
        while (!qu.isEmpty()) {
            int size = qu.size();
            list.add(qu.get(size-1).val);
            while (size > 0) {
                size--;
                TreeNode temp = qu.remove();
                if (temp.left != null) {
                    qu.add(temp.left);
                }
                if (temp.right != null) {
                    qu.add(temp.right);
                }
            }
        }
        //转换list为数组arr
        int[] arr = new int[list.size()];
        int index = 0;
        for (Integer item : list) {
            arr[index++] = item;
        }
        //返回结果
        return arr;

    }

    TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inOrder,
                   int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        int rootVal = preOrder[preStart];
        //找到中序中rootVal的位置index
        int index = inStart;
        while (index < inEnd) {
            if (inOrder[index] == rootVal) {
                break;
            }
            index++;
        }
        //确定中序左子树的长度leftsize
        int leftsize = index - inStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preOrder, preStart + 1, preStart + leftsize, inOrder, inStart,
                          index - 1);
        root.right = build(preOrder, preStart + leftsize + 1, preEnd, inOrder,
                           index + 1, inEnd);

        return root;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    List<Integer> arrayList = new ArrayList();
    public int getRootIndexInOrder(int[] xianxu, int[] zhongxu) {
        for (int i = 0; i < zhongxu.length; i++) {
            if (xianxu[0] == zhongxu[i]) return i;
        }
        return -1;
    }

    public TreeNode getRightTree(int[] xianxu, int[] zhongxu) {
        // write code here
        if (xianxu == null || xianxu.length == 0) return null;
        int preLength = xianxu.length;
        int inOrderLength = zhongxu.length;
        // 创建树根
        TreeNode root = new TreeNode(xianxu[0]);

        int index = getRootIndexInOrder(xianxu, zhongxu);
        // 先序：[1,2,4,5,3]
        // 中序：[4,2,5,1,3]
        root.left = getRightTree(
                        Arrays.copyOfRange(xianxu, 1, index + 1),
                        Arrays.copyOfRange(zhongxu, 0, index)
                    );
        root.right = getRightTree(
                         Arrays.copyOfRange(xianxu, index + 1, preLength),
                         Arrays.copyOfRange(zhongxu, index + 1, inOrderLength)
                     );
        return root;
    }

    public void getRightViewList(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
                if (size == 0) arrayList.add(poll.val);
            }
        }
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = getRightTree(xianxu, zhongxu);
        getRightViewList(root);
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        //1、重建树
        TreeNode root = rebuildTree(xianxu, zhongxu);
        //2、右视图
        List<Integer> list = new ArrayList<>();
        rightview(root, 0, list);
        //3、将list变为int[]
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;

    }
    private TreeNode rebuildTree(int[] xianxu, int[] zhongxu) {
        int pl = xianxu.length;
        int ml = zhongxu.length;
        //分治算法
        if (pl == 0 || ml == 0) return null;
        TreeNode node = new TreeNode(xianxu[0]);//根
        //找到中序根中对应的第一个序号
        for (int i = 0; i < ml ; i++) {
            if (xianxu[0] == zhongxu[i]) {
                node.left = rebuildTree(Arrays.copyOfRange(xianxu, 1, i + 1),
                                        Arrays.copyOfRange(zhongxu, 0, i));
                node.right = rebuildTree(Arrays.copyOfRange(xianxu, i + 1, pl),
                                         Arrays.copyOfRange(zhongxu, i + 1, ml));
                break;
            }
        }
        return node;
    }

    private void rightview(TreeNode root, int height, List<Integer> list) {
        if (root == null) return ;
        if (height == list.size()) list.add(0); //每层初始化为0
        list.set(height++,
                 root.val); //按照从左到右的顺序，某个高度的最后一个值必为右
        rightview(root.left, height, list);
        rightview(root.right, height, list);
    }

}

import java.util.*;


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

        return array;

    }


    private TreeNode doReConstruct(int[] pre, int[] vin, int prestart, int preend,int vinstart,int vinend) {
        if(prestart > preend || vinstart > vinend) {
            return null;
        }
        int val = pre[prestart];
        TreeNode root = new TreeNode(val);
        for(int i = vinstart;i<=vinend;i++) {
            if (vin[i] == val) {
                root.left = doReConstruct(pre, vin, prestart+1, prestart+i-vinstart,vinstart, i-1);
                root.right = doReConstruct(pre,vin,prestart+i-vinstart+1, preend, i+1, vinend);
            }
        }
        return root;

    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        //利用二维数组装层序遍历的结果，每一层为一个一维数组
        //最后返回每一层的最后一个数据即可
        TreeNode head=make(xianxu,zhongxu);
        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(head);
        while(!queue.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            int n=queue.size();
            for(int i=0;i<n;i++){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
            }
            result.add(list);
        }
        int[] res=new int[result.size()];
        for(int i=0;i<result.size();i++){
            for(int j=0;j<result.get(i).size();j++){
                if(j==result.get(i).size()-1){
                    res[i]=result.get(i).get(j);
                }
            }
        }
        return res;
        
        
    }
    //中序遍历和前序遍历合并出二叉树
    public TreeNode make(int[] pre,int[] infix){
        int m=pre.length;
        int n=infix.length;
        if(m==0 || n==0){
            return null;
        }
        TreeNode head=new TreeNode(pre[0]);
        for(int i=0;i<n;i++){
            if(pre[0]==infix[i]){
                head.left=make(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(infix,0,i));
                head.right=make(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(infix,i+1,infix.length));
            }
        }
        return head;
    }
}

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);
    } 
}