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

思路:
1.根据TOP40, 我们知道由前序遍历、中序遍历，怎么构建出一棵树
2.根据TOP26，我们知道怎么实现树的层序遍历
3.层序遍历，每层最后一个节点组成的视图就是右视图

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