題目LINK

題意解釋

這道題的意思簡單的概述就是給出二叉樹的前序遍歷和中序遍歷，讓你輸出后續(xù)遍歷。

收獲

這道題考驗了一個你對遞歸的理解以及如何用前序遍歷和中序遍歷輸出后續(xù)遍歷。整體的每次遞歸都是找出一個根結點，然后把中序序列由根結點分成兩個樹，再重復找根節(jié)點的過程，個人推薦用筆進行推下，然后再看代碼就會非常清晰。
注意：頭文件用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;
    //找到根節(jié)點
    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;
}