递归,
在中序中找前序的第一个元素,
之后切割成两个相同子问题
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector & inorder) {
if(preorder.size()==0){
return nullptr;
}
TreeNode * root = new TreeNode(preorder[0]);
vector::iterator in_mid = find(begin(inorder), end(inorder), root->val);
vector::iterator pr_mid = next(begin(preorder), 1 + in_mid - begin(inorder));
vectorleftpre = vector (next(begin(preorder)), pr_mid);
vectorleftord = vector (begin(inorder), in_mid);
root->left = buildTree( leftpre, leftord );
vectorrightpre = vector (pr_mid, end(preorder));
vectorrightord = vector (next(in_mid), end(inorder));
root->right = buildTree(rightpre,rightord);
return root;
}
};