Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution: Just do it recursively.
TreeNode *build(vector<int> &preorder, int pstart, int pend, vector<int> &inorder, int istart, int iend) {
TreeNode * root = new TreeNode(preorder[pstart]);
int idx_root = -;
for(int i = istart; i <= iend; i ++) {
if(inorder[i] == preorder[pstart]){
idx_root = i;
break;
}
}
if(idx_root == -)
return NULL;
int left_size = idx_root - istart;
if(left_size > )
root->left = build(preorder, pstart + , pstart + left_size, inorder, istart, idx_root - );
int right_size = iend - idx_root;
if(right_size > )
root->right = build(preorder, pend - right_size + , pend, inorder, idx_root + , iend);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if(preorder.size() == || inorder.size() == || preorder.size() != inorder.size())
return NULL;
return build(preorder, , preorder.size() -, inorder, , inorder.size() - );
}