POJ 2255（水题）

题目LINK

题意解释

这道题的意思简单的概述就是给出二叉树的前序遍历和中序遍历，让你输出后续遍历。

收获

这道题考验了一个你对递归的理解以及如何用前序遍历和中序遍历输出后续遍历。整体的每次递归都是找出一个根结点，然后把中序序列由根结点分成两个树，再重复找根节点的过程，个人推荐用笔进行推下，然后再看代码就会非常清晰。
注意：头文件用cstring会CE，注意下

AC代码

#include <iostream>
#include <string>

using namespace std;

string PreString, InString;

void recovery(int Lstr1, int Rstr1, int Lstr2, int Rstr2) {
    if (Lstr2 == Rstr2)
    {
        cout << InString[Lstr2];
        return;
    }
    if (Lstr2 > Rstr2)//这是中止条件
        return;
    //找到根节点
    int i = Lstr2;
    while (PreString[Lstr1] != InString[i])
        i++;
    int mov = i - Lstr2;
    //下面是分为两颗子树，先查左边，再查右边
    recovery(Lstr1 + 1, Lstr1 + mov, Lstr2, i - 1);
    recovery(Lstr1 + mov + 1, Rstr1, i + 1, Rstr2);
    
    
    cout << InString[i];
    return;
}
int main(void){
    while (cin >> PreString >> InString) {
        recovery(0, PreString.size() - 1, 0, InString.size()-1);
        cout << endl;
    }
    return 0;
}