欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Tree Recovery,UVa536

程序员文章站 2024-03-19 09:21:10
...
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

const int MAXN = 100+10;
char pre_order[MAXN], in_order[MAXN];
char lch[MAXN], rch[MAXN];

char build_tree(int L1, int R1, int L2, int R2);
void post_order(char a);

int main()
{
	while(cin>>pre_order){
		cin>>in_order;
		int n = strlen(pre_order);
		build_tree(0,n-1,0,n-1);
		post_order(pre_order[0]);
		cout<<endl;
	}
	return 0;
}
//把pre_order[L1.....R1]和post_order[L2..R2]建成一棵树返回树根 
char build_tree(int L1, int R1, int L2, int R2)
{
	if(L2>R2) return '0';
	char root;
	root = pre_order[L1];
	int p = L2;
	while(in_order[p] != root ) p++;
	int cnt = p-L2;
	lch[root-'A'] = build_tree(L1+1,L1+cnt,L2,p-1);
	rch[root-'A'] = build_tree(L1+cnt+1, R1, p+1, R2);
	return root;
}

void post_order(char a){
	if(lch[a-'A'] != '0') post_order(lch[a-'A']);
	if(rch[a-'A'] != '0') post_order(rch[a-'A']);
	cout<<a;
	return; 
}