/**
 * 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 help(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
    TreeNode* help(vector<int>& preorder,int begin1,int end1,vector<int>& inorder,int begin2,int end2)
    {
        if(begin1>end1)
            return NULL;
        else if(begin1==end1)
            return new TreeNode(preorder[begin1]);
            
        TreeNode* root=new TreeNode(preorder[begin1]);
        int i;
        for(i=begin2;i<end2;i++)
            if(inorder[i]==preorder[begin1])
                break;
        int leftlen=i-begin2;
        //左右子树怎么分的举个例子就明白了
        root->left=help(preorder,begin1+1,begin1+leftlen,inorder,begin2,begin2+leftlen-1);
        root->right=help(preorder,begin1+leftlen+1,end1,inorder,begin2+leftlen+1,end2);
        return root;
    }
};