学步园

对于某个节点x，设以x为根节点的树在前序串中的所占位置从pl到pr，在中序串中所占位置为从il到ir。显然pre[pl]=x。
搜出x在中序串中为位置为k，即in[k] = x，那么在前序串中，x的左子树的全部节点为pre[(pl+1)…(k-il+pl)]。

对于右子树的范围：

以x为根节点的右子树的总节点数为ir-id，x在前序中的截止点为pr，所以x的右子树的截止点应当为pr-(ir-id)+1。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define OT printf
#define MAXN 100010
#define REP(i, s, e) for(i = s; i < e; i++)

template <class T>
char RD(T *x)
{
        (*x) = 0;
        char ch = getchar();
        while(ch < '0' || ch > '9') { ch = getchar(); if(ch == EOF) return EOF; }
        while(ch >= '0' && ch <= '9') { (*x) *= 10; (*x) += ch - '0'; ch = getchar(); }
        return ch;
}

int n, i;
int pre[MAXN], in[MAXN];

void gao(int pl, int pr, int il, int ir)
{
    if(pl > pr) return ;
    if(pl == pr) { OT("%8d", pre[pl]); return; }
    int id;
    REP(i, il, ir + 1) if(in[i] == pre[pl]) { id = i; break; }
    gao(pl + 1, id - il + pl, il, id - 1);
    gao(pr - (ir - id) + 1, pr, id + 1, ir);
    OT("%8d", pre[pl]);
}

int main()
{
    while(RD(&n), n)
    {
        REP(i, 0, n) RD(pre + i);
        REP(i, 0, n) RD(in + i);
        puts("Postorder Traversal:");
        gao(0, n - 1, 0, n - 1);
        puts("");
    }
    return 0;
}