输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如：前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回结果

基本思想：对二叉树分而治之，拆解为左右两部分去做：

二叉树解法思路

根据以上特点，可以按顺序完成以下工作：
前序遍历的首个元素即为根节点 root 的值；
在中序遍历中搜索根节点 root 的索引 ，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。
自此可确定 三个节点的关系 ：1.树的根节点、2.左子树根节点、3.右子树根节点（即前序遍历中左（右）子树的首个元素）。
我所编写的代码如下：

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return NULL;
        return push_it(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
private:
    TreeNode* push_it(vector<int>& preorder, vector<int>& inorder,
        int left_p,int right_p,int left_i,int right_i)
    {
        cout << left_p <<"_" <<right_p <<"_" << left_i<<endl;
        if(left_p>right_p) return nullptr;
        TreeNode* node = new TreeNode(preorder[left_p]);
        if(right_p==left_p) return node;
        auto a = find( inorder.begin()+left_i, inorder.begin()+right_i, preorder[left_p])-inorder.begin()-left_i;
        node->left = push_it(preorder , inorder, left_p+1, a+left_p, left_i, a+left_i );
        node->right = push_it(preorder ,inorder, left_p+1+a , right_p, left_i+1+a, right_i);
        return node;
    }
};

接下来，分享题解中感觉比较优雅的一个：作者：TheoWu

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //递归分治
        return recursionBuild(preorder.begin(),preorder.end(),inorder.begin(),inorder.end());
    }

    //递归分治
    TreeNode* recursionBuild(vector<int>::iterator preBegin, vector<int>::iterator preEnd,vector<int>::iterator inBegin, vector<int>::iterator inEnd )
    {
        if(inEnd==inBegin) return NULL;
        TreeNode* cur = new TreeNode(*preBegin);
        auto root = find(inBegin,inEnd,*preBegin);
        cur->left = recursionBuild(preBegin+1,preBegin+(root-inBegin)+1,inBegin,root);
        cur->right = recursionBuild(preBegin+1+(root-inBegin),preEnd,root+1,inEnd);
        return cur;
    }
};