这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
很经典的递归!
把握前序,中序,后序的特点。
前序的第一个元素是树的根,在相应中序中根以左是左子树,根以右是右子树。
注意考虑 n == 1和 n == 0 的情况。
// POJ 2255 Tree Recovery
// Tanky Woo
// Memory: 180K Time: 0MS
// Language: C++ Result: Accepted
#include
#include
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];
}