POJ 2255 Tree Recovery

很经典的递归!

把握前序,中序,后序的特点。

前序的第一个元素是树的根,在相应中序中根以左是左子树,根以右是右子树。

注意考虑 n == 1和 n == 0 的情况。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 // POJ 2255 Tree Recovery
// Tanky Woo
// Memory: 180K		Time: 0MS
// Language: C++		Result: Accepted
 
#include <iostream>
#include <string>
using namespace std;
 
//定义前序,中序,后序序列
string preord, inord, postord;
void find_postord(string preord, string inord);
 
// Blog:www.wutianqi.com
int main()
{
	while(cin >> preord >> inord)
	{
		find_postord(preord, inord);
		cout << endl;
	}
	return 0;
}
 
 
//找到ch在inord中的位置,未找到返回-1
int find_root(string inord, char ch)  
{
	int i;
	for(i = 0; i < inord.size(); ++i)
		if(ch == inord[i])
			return i;
	return -1;
}
 
//通过前序,中序输出后序
void find_postord(string preord, string inord)
{
	int n = preord.size();
	if(1 == n)   //只有一个元素则直接输出
	{
		cout << preord[0];
		return;
	}
	else if(0 == n)   //没有元素则退出
		return;
 
	int i = find_root(inord, preord[0]);
	if(i == -1)//未找到则退出
		return;
 
	//对以preord[0]为根的左子树进行递归
	string pre_temp = preord.substr(1, i);
	string in_temp = inord.substr(0, i);
	find_postord(pre_temp, in_temp);
 
 
	//对以preord[0]为根的右子树进行递归
	pre_temp = preord.substr(i+1, n-i-1);
	in_temp = inord.substr(i+1, n-i-1);
	find_postord(pre_temp, in_temp);
 
	//输出根
	cout << preord[0];
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注