acwing每日一题-4

发表于 更新于 分类于 阅读次数： 本文字数： 599 阅读时长 ≈ 1 分钟
acwing每日一题——二叉树遍历

题目

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

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

输入格式

输入包含多组测试数据。

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

输出格式

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

数据范围

输入字符串的长度均不超过 26。

输入样例：

1
2
3
4
ABC
BAC
FDXEAG
XDEFAG

输出样例：

1
2
BCA
XEDGAF

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
void cir(string a,string b){   //类似分治法
    if (b.size())
    {
        char root = a[0];
        int dis = b.find(root);
        cir(a.substr(1, dis), b.substr(0, dis));
        cir(a.substr(dis + 1), b.substr(dis + 1));
        cout << root;
    }
}
int main() {
    string a;
    string b;
    while (cin >> a)
    {
        cin >> b;
        cir(a,b);
        cout << endl;
    }
    return 0;
}