j******2
发帖数: 362 | 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);
} | g****y
发帖数: 240 | 2 left tree的post_index不对。
,
【在 j******2 的大作中提到】
: 用跟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--]);
| i***e
发帖数: 452 | | j******2
发帖数: 362 | 4 没用啊。
不知道可不可以不用recursion
【在 i***e 的大作中提到】
: 把传值改成传引用就行了
| B*******1
发帖数: 2454 | 5 你贴贴fail了哪个case
,
【在 j******2 的大作中提到】
: 用跟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--]);
| i***e
发帖数: 452 | 6 我都试过你的code， 可以过的啊。
给你贴个我写的吧 ：
TreeNode* help(vector& inorder, int startIndex, int n, vector&
postorder, int start2)
{
if(n < 1) return NULL;
TreeNode* root = new TreeNode(postorder[start2+n-1]);
if(n == 1) return root;
int index = startIndex;
for(;;index++)
if(inorder[index] == root->val)
break;
int l = index - startIndex;
root->left = help(inorder, startIndex, l, postorder,start2);
root->right = help(inorder, startIndex+l+1, n - l - 1, postorder,
start2+l);
return root;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = inorder.size();
if(n == 0) return NULL;
return help(inorder, 0, n, postorder, 0);
}
【在 j******2 的大作中提到】
: 没用啊。
: 不知道可不可以不用recursion
| i**********e
发帖数: 1145 | 7 你不能过large case是因为使用内存超过限制了。
为什么？
因为你传送 vector 可是 pass by value 阿。。
这个每一层递归都得拷贝，内存使用很大啊。
改成 pass by reference:
vector & 或者 const vector & 就行了。。。
,
【在 j******2 的大作中提到】
: 用跟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--]);
| j******2
发帖数: 362 | 8 啊，权威回答！
终于明白为什么全部leetcode都用pass by reference了。。。一直的一个puzzle。
谢谢：）
看来以后递归里的参数能用pass by reference要尽量用pass by reference。
【在 i**********e 的大作中提到】
: 你不能过large case是因为使用内存超过限制了。
: 为什么？
: 因为你传送 vector 可是 pass by value 阿。。
: 这个每一层递归都得拷贝，内存使用很大啊。
: 改成 pass by reference:
: vector & 或者 const vector & 就行了。。。
:
: ,
|
|
