传送门（题目要求每个数字不重复）

题目分析：递归

对于任意一颗树而言，前序遍历的形式总是：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

如果我们在中序遍历中定位找到根节点，那我们就可以分别知道根节点的左子树和右子树的数目，也就能在前序遍历中找到对应的左子树和右子树，如上图中用括号进行定位。

这样一来题目就分解为：根据左子树的中序遍历和前序遍历，确定左子树的二叉树形式；右子树也是这样。这明显是一个递归问题。

 

这里有一个可以优化的地方，对于前序遍历中的根节点，如果每次都遍历一遍中序遍历，找到它在中序遍历中的位置，这样的复杂度会很高。我们可以建立一个HashMap，建立 值<-->索引的map，遍历一遍中序遍历即可。具体代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <map>
using namespace std;

class Solution {
private:
    map<int, int> Index;
    
public:
    TreeNode* MyBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight){
        if(preLeft > preRight) 
            return NULL;
        
        int preRoot = preLeft;
        int pIndex = Index[preorder[preRoot]];
        TreeNode* root = new TreeNode(preorder[preRoot]);
        
        int deta = pIndex - inLeft;
        
        //递归，建立左子树
        root->left = MyBuildTree(preorder, inorder, preLeft + 1, preLeft + deta, inLeft, pIndex - 1);
        
        //递归，建立右子树
        root->right = MyBuildTree(preorder, inorder,preLeft + deta + 1, preRight, pIndex + 1, inRight);
        
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int num = inorder.size();
        for(int i = 0; i < num; i++){
            Index[inorder[i]] = i;  //将前序遍历中每个节点在中序遍历中的位置找到   
        }
        return MyBuildTree(preorder, inorder,0, num - 1, 0, num - 1);   //返回链表的头结点
    }
};