2255.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 46 行

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

char pre[30],in[30];
int lchild[30],rchild[30];

int creat( int a1, int b1, int a2, int b2 )
{
	int root;
	
	if( a1 >= b1 ) return -1;

	root = std::find( in+a2, in+b2, pre[a1] ) - in - a2;
	
	lchild[a2+root] = creat( a1+1, a1+root+1, a2, a2+root );
	rchild[a2+root] = creat( a1+root+1, b1, a2+root+1, b2 );

	return a2+root;
}

void print( int r )
{
	if( r < 0 ) return;
	
	print( lchild[r] );
	print( rchild[r] );

	printf( "%c", in[r] );
}

int main()
{
	while( scanf( "%s%s", pre, in ) == 2 )
	{
		print( creat(0, strlen(pre), 0, strlen(in) ) );

		printf("\n");
	}

	return 0;
}