首页 > 代码库 > UVa 10701 - Pre, in and post

UVa 10701 - Pre, in and post

题目:已知树的前根序,中根序遍历转化成后根序遍历。

分析:递归,DS。根据定义递归求解即可。

              前根序:根,左子树,右子树;

              中根序:左子树,根,右子树;

              每次,找到根、左子树、右子树,然后分别递归左子树,右子树,输出根即可。

说明:当时进入ACM实验室的第一个题目。

#include <iostream>
#include <cstdlib> 
#include <cstdio>

using namespace std;

char Per[55],In[55];

void post(int a, int b, int c, int d)
{
	if (a>b) return;
	int r = c;
	while (In[r] != Per[a]) r ++;
	post(a+1, a+r-c, c, r-1);
	post(a+r-c+1, b, r+1, d);
	printf("%c",Per[a]);
}

int main()
{
	int n,m;
	while (~scanf("%d",&n)) 
	for (int i = 0 ; i < n ; ++ i) {
		scanf("%d%s%s",&m,Per,In);
		post(0,m-1,0,m-1);
		printf("\n");
	}
	return 0;
}

UVa 10701 - Pre, in and post