POJ 2255 Tree Recovery

这篇博客是从旧博客 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];
}