算法思路

所有二叉树的题目大部分都可以用递归求解，先来回顾一下前序遍历和中序遍历的顺序，前序遍历为根 -> 左 -> 右，中序遍历为左 -> 根 -> 右， 和LeetCode 95. 不同的二叉搜索树 II中构造过程类似，先枚举根节点，再递归构造左右子树，然后将根节点与左右子树拼接起来，具体步骤如下：

1. 先找到根节点，前序遍历的第一个数即为根节点
2. 利用哈希表，找到根节点在中序遍历中的位置k，位置k左边的序列为其左子树的中序遍历，右边的序列为右子树的中序遍历
3. 如果位置k左边的序列长度为l，则在先序遍历中，根节点后面的l个数为左子树的前序遍历，剩下的区间为右子树的后序遍历
4. 根据左右子树的前序遍历和中序遍历，再递归求解，最后将根节点与左右子树拼接起来

C++代码

/**
 * 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:
    unordered_map<int, int> hash;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i ++) hash[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
    {
        if (pl > pr) return NULL;
        int val = preorder[pl];
        int k = hash[val]; //根节点在 中序遍历中的位置
        int len = k - il; //左子树结点个数

        auto root = new TreeNode(val);
        root -> left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
        root -> right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);

        return root;
    }
};