【每日一题】2.28 由前序遍历和中序遍历确定后序遍历

问题描述

假定一棵二叉树的每个结点都用一个大写字母描述。

给定这棵二叉树的前序遍历和中序遍历，求其后序遍历。

输入格式
输入包含多组测试数据。

每组数据占两行，每行包含一个大写字母构成的字符串，第一行表示二叉树的前序遍历，第二行表示二叉树的中序遍历。

输出格式
每组数据输出一行，一个字符串，表示二叉树的后序遍历。

数据范围
输入字符串的长度均不超过 26
输入样例：
ABC
BAC
FDXEAG
XDEFAG
输出样例：
BCA
XEDGAF

问题求解

前序遍历的第一个点一定是根。
所以在中序里面找到这个点，之后以这个点为中心分割成左右两部分。
对左右两部分分别递归就行。

#include <iostream>
#include <string>

using namespace std;


void aforder(string pre, string in){
    if(in.size()){
        char c = pre[0];
        int k = in.find(c);
        aforder(pre.substr(1, k), in.substr(0, k));
        aforder(pre.substr(k+1), in.substr(k+1));
        cout<<c;
    }
    
}

int main(){
    string a, b;
    while(cin>>a>>b){
        aforder(a,b);
        cout<<endl;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25