1096 Problem A 复原二叉树

问题 A: 复原二叉树
时间: 1 Sec 内存: 32 MB
献花: 解决: 42
[献花][花圈][TK题库]
题目描述
小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。
输入
输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。
输出
对于每组输入，输出对应的二叉树的后续遍历结果。
样例输入
DBACEGF ABCDEFG
BCAD CBAD
样例输出
ACBFGED
CDAB

#include <iostream>
#include <queue>

using namespace std;

const int MaxN = 36;
string pre,in;

typedef struct tnode
{
    char data;
    struct tnode * lchild;
    struct tnode * rchild;
}TNode;

TNode * CreateTree(int pl,int pr,int il,int ir)
{
    if(pl > pr)return NULL;

    TNode * root = new TNode;
    root->data = pre[pl];

    int k = il;
    while(k<=ir)
    {
        if(in[k] == pre[pl])
            break;
        ++k;
    }

    root->lchild = CreateTree(pl+1,pl+k-il,il,k-1);
    root->rchild = CreateTree(pl+k-il+1,pr,k+1,ir);

    return root;
}


void Post(TNode * root)
{
    if(!root) return;

    Post(root->lchild);
    Post(root->rchild);
    cout << root->data;

    delete root;
}

int main()
{
#ifdef _Debug
freopen("data.txt","r+",stdin);
#endif

    std::ios::sync_with_stdio(false);
    while(cin >> pre >> in)
    {
        TNode *root = CreateTree(0,pre.size()-1,0,in.size()-1);
        Post(root);
        cout << endl;
    }
}

/**************************************************************
    Problem: 1096
    User: Sharwen
    Language: C++
    Result: 升仙
    Time:1 ms
    Memory:1696 kb
****************************************************************/