输入格式: 两行。第一行是二叉树的前序遍历序列，第二行是中序遍历序列。每个数字表示的结点之间用空格隔开。 输出格式： 一行。由输入中的前序列和中序遍历序列重建的二叉树的后序遍历序列。每个数字表示的结点之间用空格隔开

算法1：

1. 递归

时间复杂度：$O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
int pre[MAXN], in[MAXN], post[MAXN], l[MAXN], r[MAXN];
int cnt;

int build(int il, int ir, int pl, int pr) {
    if (il > ir) return 0;
    int root = pre[pl];
    int k = l[root];
    post[cnt] = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    post[cnt] = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
    post[cnt++] = root;
    return root;
}

int main() {
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
        l[in[i]] = i;
        r[in[i]] = i;
    }
    build(0, n - 1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", post[i]);
    }
    printf("\n");
    return 0;
}

算法2：

1. 模拟栈

时间复杂度：$O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
int pre[MAXN], in[MAXN], post[MAXN];
int n, cnt, top;
int stk[MAXN];

void dfs(int il, int ir) {
    if (il > ir) return;
    int root = pre[cnt++];
    int k = il;
    while (in[k] != root) k++;
    dfs(il, k - 1);
    dfs(k + 1, ir);
    post[top++] = root;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    dfs(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", post[i]);
    }
    printf("\n");
    return 0;
}