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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        int[] ret=new int[1];
        if(xianxu.length==0){
            return new int[0];
        }
        TreeNode root=buildTree(xianxu,zhongxu);
        Queue<TreeNode> qu=new LinkedList<>();
        List<ArrayList<Integer>> list=new ArrayList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            ArrayList<Integer> list1=new ArrayList<>();
            int size=qu.size();
            for(int i=0;i<size;i++){
                TreeNode top=qu.poll();
                if(top.left!=null){
                    qu.offer(top.left);
                }
                if(top.right!=null){
                    qu.offer(top.right);
                }
                list1.add(top.val);
            }
            list.add(list1);
        }
        for(int i=0;i<list.size();i++){
            int j=0;
            for(;j!=list.get(i).size()-1;j++){
                ;
            }
            if(i==ret.length){
                ret=Arrays.copyOf(ret,ret.length+1);
            }
            ret[i]=list.get(i).get(j);
            
        }
        return ret;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return createTree(preorder, inorder, 0, preorder.length-1);
    }
    public int preIndex;
    public TreeNode createTree(int[] preorder, int[] inorder, int inbegin, int inend) {
        if (inbegin > inend) return null;
        TreeNode root = new TreeNode(preorder[preIndex]);
        int index = findIndex(inorder, inbegin, inend, preorder[preIndex]);
        preIndex++;

        root.left = createTree(preorder, inorder, inbegin, index - 1);

        root.right = createTree(preorder, inorder, index + 1, inend);
        return root;
    }

    public int findIndex(int[] inorder, int inbegin, int inend, int val) {
        int i = 0;
        for (i = inbegin; i <= inend; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;

    }
}