给出二叉树的先序遍历和中序遍历，求后序遍历。
树中结点是不重复的大写字母，因此可以直接用其ASCII码作为数组下标来建树，维护每个结点的左孩子和右孩子数组。递归建树的过程比较常规，要注意递归结束的条件。
Problem.png
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string pre, in;
const int maxn = 256;
int lch[maxn], rch[maxn];
// 当前递归到的这棵树
// 先序下标范围 L1 --- R1
// 中序下标范围 L2 --- R2
int recov(int L1, int R1, int L2, int R2) {
// 注意递归结束条件
if (L1 > R1) return 0;
int root = pre[L1];
int i = L2;
while (in[i] != root) i++;
// 左子树中序 L2 --- i - 1
// 右子树中序 i + 1 --- R2
int l_n = i - L2;
// 左子树先序 L1 + 1 --- L1 + l_n
// 右子树先序 L1 + l_n + 1 --- R1
lch[root] = recov(L1 + 1, L1 + l_n, L2, i - 1);
rch[root] = recov(L1 + l_n + 1, R1, i + 1, R2);
return root;
}
void post_order(int root) {
// 注意递归结束条件
if (root == 0) return;
post_order(lch[root]);
post_order(rch[root]);
printf("%c", root);
}
int main() {
while (cin >> pre >> in) {
int len1 = pre.length(), len2 = in.length();
int root = recov(0, len1 - 1, 0, len2 - 1);
post_order(root);
cout << endl;
}
return 0;
}
