题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8）。

输入格式
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式
1行，表示一棵二叉树的先序。

输入示例：
BADC
BDCA

输出示例：
ABCD

题解

题解
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
26
#include <iostream>

using namespace std;

string mid, aft;//中序和后序

void before(string mid, string aft){
    if(mid.size() > 0){
        char ch = aft[aft.size() - 1];//取出头结点，输出
        cout << ch;
        int k = mid.find(ch);//找到头结点在中序序列中的位置，以这个位置为结点，将中序序列和后序序列分								成两部分，递归处理
        before(mid.substr(0, k), aft.substr(0, k));//前半部分
        before(mid.substr(k + 1), aft.substr(k, mid.size() - k - 1));//后半部分
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> mid >> aft;
    
    before(mid, aft);
    
    return 0;
}