上海市计算机学会竞赛平台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;
}