/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    // 对于一颗二叉树，前序遍历的第一个值是根节点的值，根据根节点的值和中序遍历可以得到左右子树
    // 递归的得到左右子树的根节点
    // 从先序遍历中取出第一个元素创建根节点。
    // 在中序遍历中找到该根节点的位置，这将中序遍历分为两部分，左边是树的左子树，右边是树的右子树。
    // 递归地使用左子树的先序和中序遍历结果重建左子树。
    // 递归地使用右子树的先序和中序遍历结果重建右子树。
    // 返回根节点
   int preIndex = 0;
    HashMap<Integer, Integer> hs = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            hs.put(inorder[i], i);
        }
        return buildTreeRecursive(preorder, 0, inorder.length - 1);    
    }
    // recursive 递归
    // 利用前序遍历的顺序构建子树，中序遍历得到左子树和右子树的范围
    public TreeNode buildTreeRecursive(int[] preorder, int left , int right) {
        if (left > right) {
            return null;
        }
        int rootVal = preorder[preIndex++]; // 前序遍历的第一个节点总是当前子树的根
        TreeNode root = new TreeNode(rootVal);
        int index = hs.get(rootVal);
        root.left = buildTreeRecursive(preorder, left, index - 1);
        root.right = buildTreeRecursive(preorder, index + 1, right);
        return root;
    }
   
}