Contest1345/G.cpp

#include <bits/stdc++.h>
using namespace std;
typedef struct BinTree
{
    char data;
    BinTree* lchild;
    BinTree* rchild;
} BinTree;
void RebuildTree(BinTree* &Tree,char *pre,char *in,int len)
{
    Tree = new BinTree;
    if(Tree!=NULL)
    {
        if(len<=0)//递归截止条件
        {
            Tree = NULL;
            return ;
        }
        int index = 0;
        while(index<len&&*(pre)!=*(in+index))
        {
            //寻找当前的root结点（包含子树）
            index++;
        }
        Tree->data = *(pre);
        RebuildTree(Tree->lchild,pre+1,in,index);//去掉root结点
        RebuildTree(Tree->rchild,pre+1+index,in+1+index,len-(index+1));//去掉左边和根节点
    }
    return ;
}
void PostOrderTravese(BinTree* Tree)
{
    //后序遍历输出
    if(Tree==NULL)
        return;
    PostOrderTravese(Tree->lchild);
    PostOrderTravese(Tree->rchild);
    cout<<Tree->data;
}
int main()
{
    char pre[101];  //string pre;
    char in[101];   //string in;
    while(cin>>pre>>in)
    {
        BinTree* tree;
        int length = strlen(pre);
        RebuildTree(tree,pre,in,length);
        PostOrderTravese(tree);
        cout<<endl;
    }
    return 0;
}