postorder.cpp

// construct the post transverse based on the preorder and inorder transverse
// lrj whitebook p106
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>

using namespace std;
const int MAXN = 100;

void postorder(char* pre, char* pre_end, char *in, char *in_end){
    if(pre > pre_end){
        return;
    }
    if(pre == pre_end){
        cout << *pre << " ";
    }else{
        char * index = strchr(in, *pre);
        postorder(pre+1, pre+(index-in), in, index-1);
        postorder(pre+(index-in)+1, pre_end, index+1, in_end);
        cout << *index << " ";
    }

}
int main(){
    char prebuf[MAXN];
    char inbuf[MAXN];
    int len = 0;
    while(scanf("%s%s", prebuf, inbuf) != -1){
        //printf("%s %s\n", prebuf, inbuf);
        len = strlen(prebuf);
        postorder(prebuf, prebuf+len-1, inbuf, inbuf+len-1);
        cout << endl;
    }
}