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

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 new int[]{};
        }
        
        TreeNode root = make(xianxu, 0 ,xianxu.length -1 , zhongxu, 0, zhongxu.length -1);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode temp = null;
        List<Integer> result = new ArrayList<Integer>();
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                size --;
                temp = queue.poll();
                if(temp.left != null){
                    queue.add(temp.left);
                }
                if(temp.right != null){
                    queue.add(temp.right);
                }
                
            }
            result.add(temp.val);
        }
        return result.stream().mapToInt(Integer::valueOf).toArray();
        
        
    }
    private TreeNode make(int[] pre, int preStart, int preEnd, int[] middle, int middleStart,int middleEnd){
        TreeNode node = new TreeNode(0);
        node.val = pre[preStart];
        int endIndex = preStart;
        //找到中序遍历数组中 根节点位置
        for(int i = middleStart;i<= middleEnd;i++){
            if(middle[i] == pre[preStart]){
                endIndex = i;
                break;
            }
        }
        int leftOffset = endIndex - middleStart;
        if(leftOffset > 0){
            node.left = make(pre, preStart+1, preStart + leftOffset, middle,middleStart,endIndex -1);

        }
        int rightOffset = middleEnd - endIndex;
        if(rightOffset >0){
             node.right = make(pre, preStart+leftOffset+1, preEnd, middle, endIndex + 1, middleEnd);
        }
        
        return node;
    }
}