105. 从前序与中序遍历序列构造二叉树1️⃣

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int prelength = preorder.length;
        int inlength = inorder.length;
        Map<Integer, Integer> inorderMap = new HashMap();
        for (int i = 0; i < inlength; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, prelength - 1, inorderMap, 0, inlength - 1);
    }
    public TreeNode buildTree(int[] preorder, int preLeft, int preRight, Map<Integer, Integer> inorderMap, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return null;
        }
        int val = preorder[preLeft];
        TreeNode root = new TreeNode(val);
        int pIndex = inorderMap.get(val);
        root.left = buildTree(preorder, preLeft + 1, preLeft + pIndex - inLeft, inorderMap, inLeft, pIndex - 1);
        root.right = buildTree(preorder, preLeft + pIndex - inLeft + 1, preRight, inorderMap, pIndex + 1, inRight);
        return root;
    }
}