/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer, Integer> indexForInOrders = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i =0; i < inorder.length; i++) {
            indexForInOrders.put(inorder[i], i);
        }
        return buildTree(preorder, inorder,0, preorder.length - 1,0, inorder.length - 1);
    }

    /**
     *
     * @param pre
    - pre_l：                 表示当前根结点所代表的树在前序遍历序列中对应范围的起点位置。
    - pre_r：               表示当前根结点所代表的树在前序遍历序列中对应范围的终点位置。
    - in_l：                表示当前根结点所代表的树在中序遍历序列中对应范围的起点位置。
    - in_r：                表示当前根结点所代表的树在中序遍历序列中对应范围的终点位置。
     * @return
     */
    private TreeNode buildTree(int[] pre,int[] inorder, int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }

        //根节点
        TreeNode root = new TreeNode(pre[preL]);
        // 从这个节点开始切分 中序数组
        Integer inIndex = indexForInOrders.get(root.val);

        int leftTreeSize = inIndex - inL;
        root.left = buildTree(pre, inorder, preL + 1, preL+ leftTreeSize, inL, inIndex -1);
        root.right = buildTree(pre, inorder, preL + 1 + leftTreeSize, preR, inIndex + 1, inR);
        return root;
    }
}