拷的POJ的代码,直接A了。
/* ID:bysen LANG:C++ PROG:heritage */ #include<iostream> #include<stdio.h> #include<string> #include<fstream> using namespace std; ifstream fin("heritage.in"); ofstream fout("heritage.out"); int strlen( char *a ) { int i; for( i=0;a[i]!='\0';i++ ) ; return i; } void DG( char *a,char *b ) { int left=0,right=strlen(a)-1; if( strlen(a)==1 ) { fout<<a[0]; return ; } int left1,right1; //left right1 left1 right char root=a[0]; int index=0; left++; while( b[index]!=root ) index++;//通过中序遍历找分划点 right1=index; left1=right1+1; if( left==right ) fout<<a[right]; else { char a1[100],b1[100]; char a2[100],b2[100]; int i; int flag=left; for( i=0;flag<=right1;flag++ ) a1[i++]=a[flag]; a1[i]='\0'; for( i=0;i<index;i++ ) b1[i]=b[i]; b1[i]='\0'; flag=left1; for( i=0;flag<=right;flag++ ) a2[i++]=a[flag]; a2[i]='\0'; flag=index+1; for( i=0;flag<=right;flag++ ) b2[i++]=b[flag]; b2[i]='\0'; if( left<=right1 ) DG( a1,b1 ); if( left1<=right ) DG( a2,b2 ); } fout<<root; } int main() { char dateP[100]; char dateM[100]; fin>>dateM>>dateP; DG( dateP,dateM ); fout<<endl; return 0; }