536 - Tree Recovery

[limelight_team]

could anybody give me a hint on what algorithm might be used on this problem?

[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

[limelight_team]

Thanks a lot, cyfra, I got p.536 AC'd.

[ffkre]

i got WA, any test case???

[hank]

What's your method?

[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?

[Eric]

Finally I get accepted.
My array is a little bit (just a '[') too small and cause my counting sort fail.

[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.

[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.

[I LIKE GN]

hello...
i can't figure out of RTE...
would u please help???????

Code: Select all

ACed...// removed

thanks.

[I LIKE GN]

please help meeeeeee!!!!!!!!!!

[I LIKE GN]

[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:

Code: Select all

ABCEDFGH ECBDFAHG

[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]

[Johan]

Well it worked with only minor changes for a quite similar problem here in the archive, so I'll count the point. Thanks.