思路：

1. 先利用前序遍历找根节点：前序遍历的第一个数，就是根节点 root 的值；
2. 在中序遍历中找到根节点的位置 rootInLocal，则 rootInLocal 左边是左子树的中序遍历，右边是右子树的中序遍历；所以得建立一个hash表记录这个位置hash[inorder[i]] = i(本题中二叉树中每个节点的值都互不相同)
3. 递归生成左右子树, [pl, pl] 为前序区间, [il, il] 为中序区间。
   3.1 左子树前序区间为[pl + 1, pl + rootInLocal - il]。
   pr 已为根节点，则 pl + 1 为左子树的根节点，所以pl + 1为前序区间左端点。pr + rootInLocal - i为前序区间右端点。左子树中元素个数 = 中序遍历中左子树根节点的位置(rootInLocal) - 中序遍历中左端点(il)。为什么不加一，因为一是左子树的父节点。
   3.2 左子树中序区间为[il, rootInLocal - 1]。根节点(不包括)左边都是左子树的区间
   3.3 右子树前序区间为[pl + rootInLocal - il + 1, pr]。左子树前序区间的后面都是右子树的前序区间
   3.4 右子树中序区间为[rootInLocal + 1， ir]。根节点(不包括)右边都是右子树的区间
4. 构建完根、左右子树后直接返回。如果前序左端点大于右端点，说明正在构建以叶子节点为根的子树，而叶子的出度是为0的，所以直接返回空即可。

Java

时间复杂度：O(nlogn + n)

空间复杂度：O(n)

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private static HashMap<Integer, Integer> hash = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; ++i) {
            hash.put(inorder[i], i);
        }
        return dfs(0, preorder.length - 1, 0, inorder.length - 1, preorder);
    }

    public static TreeNode dfs(int pl, int pr, int il, int ir, int[] pre) {
        if(pl > pr) return null;
        TreeNode root = new TreeNode(pre[pl]);
        int rootInLocal = hash.get(root.val);
        root.left = dfs(pl + 1, pl + rootInLocal - il, il, rootInLocal - 1, pre);
        root.right = dfs(pl + rootInLocal - il + 1, pr, rootInLocal + 1, ir, pre);
        return root;
    }
}

C++

时间复杂度：O(nlogn + n)

空间复杂度：O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int, int> hash;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;
        return dfs(0, preorder.size() - 1, 0, inorder.size() - 1, preorder);
    }

    TreeNode* dfs(int pl, int pr, int il, int ir, vector<int> &pre) {
        if(pl > pr) return NULL;
        TreeNode* root = new TreeNode(pre[pl]);
        int rootInLocal = hash[root->val];
        root->left = dfs(pl + 1, pl + rootInLocal - il, il, rootInLocal - 1, pre);
        root->right = dfs(pl + rootInLocal - il + 1, pr, rootInLocal + 1, ir, pre);
        return root;
    }
};