class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(0 == preorder.size() || 0 == inorder.size()) return NULL;
return build(preorder, inorder, 0, inorder.begin(), inorder.end());
}
TreeNode *build(vector<int>& preorder, vector<int>& inorder, int rootPreIndex, vector<int>::iterator Instart,
vector<int>::iterator Inend)
{
if(rootPreIndex >= preorder.size() || Inend <= Instart) return NULL;
auto target = find(Instart, Inend, preorder[rootPreIndex]);
if(target != inorder.end()){
TreeNode *root = new TreeNode(preorder[rootPreIndex]);
root->left = build(preorder, inorder, rootPreIndex+1, Instart, target);
root->right = build(preorder, inorder, rootPreIndex + target - Instart + 1, target+1, Inend);
return root;
}
else{
return NULL;
}
}
};
