二叉树的题目基本上都是要用递归的,这题也一样。
而递归的核心是找到结构相同的子问题。
二叉树如下所示:
a
↙ ↘
b c
↙↘ ↘
d e g
前序: abdecg
中序: dbeacg
由前序的第一个a,可以把树分为两个部分,左子树和右子树。
在中序序列中找到a,左边部分则是左子树的中序,右边则是右子树的中序,
同样前序a的后面紧跟着左子树的前序和右子树的前序。
则问题可分解为两个结构相同的小问题。
1,先求左子树的后序;
2,求右子树的后序;
3,再将左子树和右子树的后序串起来,最后加上本身节点即可。
代码:
-
#include
-
#include
-
using namespace std;
-
-
string FindPostOrder( string pre_order, string in_order );
-
-
int _tmain(int argc, _TCHAR* argv[])
-
{
-
string pre_order, in_order, post_order;
-
cin >> pre_order >> in_order;
-
cout << FindPostOrder( pre_order, in_order );
-
return 0;
-
}
-
-
string FindPostOrder( string pre_order, string in_order )
-
{
-
if( pre_order.length() != in_order.length() )
-
{
-
cout << "Failed" << endl;
-
exit(1);
-
}
-
-
if( pre_order.length() == 1 )
-
{
-
if( pre_order != in_order )
-
{
-
cout << "Failed" <
-
exit(1);
-
}
-
return pre_order;
-
}
-
-
if( pre_order.length() == 0)
-
return string();
-
-
char node = pre_order[0];
-
int index = in_order.find( node );
-
-
if( index == string::npos )
-
{
-
cout << "Failed" <
-
exit(1);
-
}
-
int len = pre_order.length();
-
-
-
string left_part = FindPostOrder( pre_order.substr(1,index), in_order.substr(0,index) );
-
-
string right_part = FindPostOrder( pre_order.substr(1+index, len-index-1), in_order.substr(1+index,len-index-1) );
-
-
return left_part+right_part+node;
-
-
}
阅读(1413) | 评论(0) | 转发(0) |