上海市计算机学会竞赛平台2022年9月月赛丙组二叉树的遍历

题目描述

有一棵二叉树，结点数量不超过 2626 个，树上的每个结点都有一个大写字母。

给定这棵二叉树的前序遍历及中序遍历，请输出它的后序遍历。

输入格式

• 第一行：一个字符串，表示二叉树的前序遍历；
• 第二行：一个字符串，表示二叉树的中序遍历。

输出格式

• 单独一行：一个字符串，表示二叉树的后序遍历。

数据范围

设输入的字符串长度为 𝑛n，

• 对于 50%50% 的数据，1≤𝑛≤101≤n≤10
• 对于 100%100% 的数据，1≤𝑛≤261≤n≤26

样例数据

输入:

ACE
CAE

输出:

CEA

详见代码:

#include <bits/stdc++.h>
using namespace std;
string q, z;
void dfs(int ql, int zl, int len) 
{int i;int lenz, leny;for (i = 0; i < len; i++) {if(q[ql] == z[zl + i]) break;}lenz = i;leny = len - i - 1;if (lenz > 0)dfs(ql + 1, zl, lenz);if (leny > 0)dfs(ql + 1 + lenz, zl + 1 + lenz, leny);cout << q[ql];return;
}
int main() 
{int len;cin >> q >> z;len = q.length();dfs(0, 0, len);return 0;
}