Page 1 of 2
536 - Tree Recovery
Posted: Tue Jan 29, 2002 5:24 am
by limelight_team
could anybody give me a hint on what algorithm might be used on this problem?
Posted: Wed Jan 30, 2002 11:55 am
by cyfra
Hi!
This is quite an easy task.
You have to do this using recurence.
in the input the first letter is the root.
If you find this letter in the inord reprezentation you will know the length of the left and right subtree. And now you can do the same with left subtree... ( the second letter in preord is its root)..
And using the recurence you can do it with all tree...
I hope it will help
Posted: Wed Jan 30, 2002 2:07 pm
by limelight_team
Thanks a lot, cyfra, I got p.536 AC'd.
536 get WA. any test case,help~~~~~~~
Posted: Sun Feb 23, 2003 12:28 pm
by ffkre
i got WA, any test case???
Posted: Fri Mar 14, 2003 5:32 pm
by hank
What's your method?
Posted: Sun Apr 13, 2003 12:06 pm
by Eric
[pascal]Deleted as I get accepted[/pascal]
I am not familiar with the binary tree.
Can anyone tell me why I get WA?
I only know that the 1st letter in the pre-order is the root and the total number of path is N-1.
Can anyone give me some sample input/output?
Posted: Mon Apr 14, 2003 9:51 am
by Eric
Finally I get accepted.
My array is a little bit (just a '[') too small and cause my counting sort fail.
Posted: Wed Jan 14, 2004 4:57 pm
by Grinder
Hi, Can any one help why RUNTIME ERROR:
This is my code:
Code: Select all
#include <stdio.h>
#include <string.h>
#define MAX 100
int findRoot(char in[],char item)
{
int i;
for(i = 0; i < strlen(in); i++)
if(in[i] == item)
return i;
return 0;
}
void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
int root;
if(in_low > in_up) return;
if(in_low == in_up)
{
printf("%c",in[in_low]);
return;
}
root = findRoot(in,pre[pre_low]);
if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
printf("%c",in[root]);
}
void main()
{
char prefix[MAX];
char infix[MAX];
while(scanf("%s %s",prefix,infix) == 2)
{
postfix(prefix,0,infix,0,strlen(infix)-1);
printf("\n");
}
}
Plz help me.
Posted: Wed Jan 14, 2004 4:58 pm
by Grinder
Hi, Can any one help why RUNTIME ERROR:
This is my code:
Code: Select all
#include <stdio.h>
#include <string.h>
#define MAX 100
int findRoot(char in[],char item)
{
int i;
for(i = 0; i < strlen(in); i++)
if(in[i] == item)
return i;
return 0;
}
void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
int root;
if(in_low > in_up) return;
if(in_low == in_up)
{
printf("%c",in[in_low]);
return;
}
root = findRoot(in,pre[pre_low]);
if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
printf("%c",in[root]);
}
void main()
{
char prefix[MAX];
char infix[MAX];
while(scanf("%s %s",prefix,infix) == 2)
{
postfix(prefix,0,infix,0,strlen(infix)-1);
printf("\n");
}
}
Plz help me.
RTEEEEE
Posted: Fri Sep 16, 2005 6:24 pm
by I LIKE GN
hello...
i can't figure out of RTE...
would u please help???????
thanks.
Posted: Tue Sep 20, 2005 4:37 pm
by I LIKE GN
please help meeeeeee!!!!!!!!!!
Posted: Tue Oct 25, 2005 12:51 pm
by I LIKE GN
Posted: Fri Oct 28, 2005 5:05 pm
by roticv
Grinder, your code's
Code: Select all
if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
is wrong.
If anyone is basing your algorithm on his, try the following test case:
536 wa
Posted: Sat May 06, 2006 2:22 pm
by Johan
Hi,
My 536 passes the example testcase, but a submission results in a wrong answer. Does anybody have a hint or perhaps some nice testcases?
The idea behind the code below is this:
1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree
Kind regards,
Johan
Code: Select all
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<vs> vvs;
#define pb push_back
#define sz(v) ((int)(v).size())
vs splitvs(string s,string split)
{
vs uit; string nu;
split+=char(0); s+=char(0);
for(int i=0;i<sz(s);i++)
{
if(split.find(s[i])!=string::npos)
{ if(sz(nu)>0)uit.pb(nu); nu=""; }
else nu+=s[i];
}
return uit;
}
void go(vi left,vi right,int current)
{
if(left[current]!=-1) go(left,right,left[current]);
if(right[current]!=-1) go(left,right,right[current]);
printf("%c",current+64);
}
void fill(vi &left, vi &right, string pre, string in)
{
char root=pre[0];
int r=in.find(root);
string lin=in.substr(0,r), rin=in.substr(r+1), lpre, rpre;
for(int i=1;i<sz(pre);i++)
if(lin.find(pre[i])!=string::npos)
lpre+=pre[i];
else
rpre+=pre[i];
if(sz(lpre)>0)
{
left[root-64]=lpre[0]-64;
fill(left,right,lpre,lin);
}
if(sz(rpre)>0)
{
right[root-64]=rpre[0]-64;
fill(left,right,rpre,rin);
}
}
int main()
{
char buffer[1000];
while(gets(buffer))
{
vs p=splitvs(buffer," ");
if(sz(p)==0)
{ printf("\n"); continue; }
string pre=p[0],in=p[1];
vi left(26,-1), right(26,-1);
//build tree
fill(left,right,pre,in);
//traverse tree
go(left,right,pre[0]-64); printf("\n");
}
return 0;
}
[/code]
Posted: Tue May 09, 2006 4:39 am
by Johan
Well it worked with only minor changes for a quite similar problem here in the archive, so I'll count the point. Thanks.
