Online Judge►UVa

[UVa] 536 - Tree Recovery

題意

給Tree的Preorder和Inorder，求出Postorder。

解法

Preorder (root, left subtree, right subtree)
Inorder (left subtree, root, right subtree)
Postorder (left subtree, right subtree, root)

所以對於preorder來說，最接近左邊的是某子樹的root，而該root對應到inorder中可知左部分是left subtree，而右部分是right subtree，而由於postorder先left再right，所以遞迴要先進行right subtree。

以範例來說：DBACEGF ABCDEFG

1
2
3
[D]		ABCDEFG中在preorder中最左邊的是D，所以D是該樹的root，可知ABC是left而EFG是right。
[ED]		EFG在preorder中最左邊的是E，所以E是該子樹的root，沒有left而FG是right。
[GED]	FG在preorder中最左邊的是G，所以G是該子樹的root，F是left而沒有right。

依此類推即可。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
int fillsite ;
string a , b ;
char c[26] ;
int length ;
void findRoot(int l , int r){
	if ( l >= r  )
		return ;
	char root ;
	int rootsite ;
	bool isFind = false ;
	for ( int i = 0 ; i < length ; i ++ ){
		for ( int j = l ; j < r ; j ++ ){
			if ( a[i] == b[j] ){
				isFind = true ;
				rootsite = j ;
				root = a[i] ;
				break ;
			}
		}
		if ( isFind == true )
			break ;
	}
	c[fillsite] = root ;
	fillsite -- ;
	findRoot(rootsite+1,r);
	findRoot(l,rootsite) ;
}
int main()
{
	while ( cin >> a >> b ){
		length = a.length() ;
		fillsite = length - 1 ;
		findRoot(0,length) ;
		for ( int i = 0 ; i < length ; i ++ )
			cout << c[i] ;
		cout << endl ;
	}
	return 0;
}