【题目来源】
洛谷：[P1827 USACO3.4] 美国血统 American Heritage - 洛谷
【题目描述】
农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 26 个的顶点。
这是在样例输入和样例输出中的树的图形表达方式：
C/ \/ \B G/ \ /A D H/ \E F
【输入】
第一行一个字符串，表示该树的中序遍历。
第二行一个字符串，表示该树的前序遍历。
【输出】
单独的一行表示该树的后序遍历。
【输入样例】
ABEDFCHG
CBADEFGH
【输出样例】
AEFDBHGC
【解题思路】
【算法标签】
《洛谷 P1827 美国血统》 #模拟# #树形数据结构# #递归# #构造# #USACO#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
string a, b;
// char a[30], b[30];
void f(int al, int ar, int bl, int br)
{int ak, ln, rn; // 定义a中ak（即中序遍历中的根节点）for (int i=al; i<ar; i++) { // 遍历a字符串if (a[i]==b[bl]) { // 根据b中第一个字符，即根节点，找到a中根节点的位置ak = i; // 记录其位置break; // 退出循环}}ln = ak-al; // 得到左子树的字符长度rn = ar-(ak+1); // 以及右子树的字符长度if (ln>0) { // 如果左子树长度不为0f(al, al+ln, bl+1, bl+1+ln); // 传入中序和前序字符串的起始和终止位置}if (rn>0) { // 如果右子树长度不为0f(ak+1, ak+1+rn, br-rn, br); // 传入中序和前序字符串的起始和终止位置}cout << b[bl]; // 直到只有1个字符的情况，打印这个字符return;
}
int main()
{cin >> a >> b; // 以字符串形式读入中序遍历和前序遍历字符串int n = a.length(); // 得到字符串长度int al = 0, ar = n, bl = 0, br = n; // 定义a和b字符串的起始和结束为止f(al, ar, bl, br); // 传入f递归函数中return 0;
}
【运行结果】
ABEDFCHG
CBADEFGH
AEFDBHGC