[leetcode] Binary Tree from Inorder & Postorder Traversal# JobHunting - 待字闺中
j*2
1 楼
用跟preorder+inorder construct tree类似的方法，死活过不了大的test，高手给指
点指点？
TreeNode *build(vector in, vector post, int in_start, int in_end,
int & post_index)
{
if(in_start>in_end)
{
return NULL;
}
TreeNode *r=new TreeNode(post[post_index--]);
if(in_start==in_end)
{
return r;
}
int in_index=search(in, in_start, in_end, r->val);
r->right=build(in, post, in_index+1, in_end, post_index);
r->left=build(in, post, in_start, in_index-1, post_index);
return r;
}
int search(vector v, int start, int end, int target)
{
int i;
for(i=start; i<=end; i++)
{
if(v[i]==target)
{
return i;
}
}
return 0;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
int n=postorder.size()-1;
return build(inorder, postorder, 0, n, n);
}
点指点？
TreeNode *build(vector
int & post_index)
{
if(in_start>in_end)
{
return NULL;
}
TreeNode *r=new TreeNode(post[post_index--]);
if(in_start==in_end)
{
return r;
}
int in_index=search(in, in_start, in_end, r->val);
r->right=build(in, post, in_index+1, in_end, post_index);
r->left=build(in, post, in_start, in_index-1, post_index);
return r;
}
int search(vector
{
int i;
for(i=start; i<=end; i++)
{
if(v[i]==target)
{
return i;
}
}
return 0;
}
TreeNode *buildTree(vector
int n=postorder.size()-1;
return build(inorder, postorder, 0, n, n);
}
