poj2255

题目链接

题意：给一棵树的先序遍历和中序遍历，求它的后序遍历

思路：先序遍历提供每一棵子树的根结点，利用中序遍历找出左子树，同时即可得到右子树，然后递归两子树，最后输出根结点，即可得到后序遍历

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

void build(int len,char* s1,char* s2)
{
    if(len<=0)
        return;
    int p=strchr(s2,s1[0])-s2;
    build(p,s1+1,s2);
    build(len-p-1,s1+p+1,s2+p+1);
    printf("%c",s1[0]);
}


int main()
{
    char s1[27],s2[27];
    while(scanf("%s %s",s1,s2)!=EOF)
    {
        int len=strlen(s1);
        build(len,s1,s2);
        printf("\n");
    }
    return 0;
}