536 - Tree Recovery

[mukeshtiwari]

hello everybody i am not very comfortable with recursion but i tried to solve this problem according to above give algorithm but getting RTE . plz help me and give me some recursion problems . it will be very helpful to me .
thankx

Code: Select all

#include<stdio.h>
#include<string.h>

char  pre[300],in[300];

	void fun(int pl,int pr,int il,int ir)
		{
			int r,lsize,rsize;
			for(r=il;r<=ir;r++)
				if(pre[pl]==in[r])
					break;
			lsize=r-il;
			rsize=ir-r;
			if(lsize>0)
				fun(pl+1,pl+lsize,il,r-1);
			if(rsize>0)
				fun(pl+lsize+1,pr,r+1,ir);

			printf("%c",in[r]);
		}
	int main()
		{
			int n;
			while(scanf("%s%s",pre,in)==2)
			 {

				n=strlen(pre);
				fun(0,n-1,0,n-1);
				printf("\n");
			  }
		}

[turcse143]

A simple recursion problem:

I think your code is crash here:

lsize=r-il;
rsize=ir-r;
if(lsize>0)
fun(pl+1,pl+lsize,il,r-1);
if(rsize>0)
fun(pl+lsize+1,pr,r+1,ir);

check it again.
You may do:
---->find the root from pre & in. mark it.
---->find the right child & mark it.
---->find the left child.
---->then call a fucntion recursively.

u will get the sequence:
left--->root--->right.

hope it will work

[newton]

Code: Select all

Accepted !

[mf]

Because string.h declares a function called "index".
Change the name of your variable, or create and put it in your own namespace (if you use C++.)

You can try 10410 as a more challenging problem of this kind.

[aeiou]

Hi ,
Removed after AC