1020. Tree Traversals (25)

the problem is from pat,which website is http://pat.zju.edu.cn/contests/pat-a-practise/1020

and the source code is as followed.

#include<iostream>
#include<cstdlib>
#include<queue>

using namespace std;

const int maxx = 32;

typedef struct Tree
{
    Tree *le;
    Tree *ri;
    int data;
}Tree;

Tree *root;

int pos[maxx],in[maxx];

void printLevelOrder(Tree *root)
{
    queue<Tree*> que;
    Tree *tr = NULL;
    que.push(root);
    bool flg = true;
    while (!que.empty())
    {
        tr = (Tree *)que.front();
        que.pop();
        if (tr == NULL) continue;
        if (flg)
        {
            printf("%d",tr->data);
            flg = false;
        }else
        {
            printf(" %d",tr->data);
        }
        que.push(tr->le);
        que.push(tr->ri);
    }
    printf("
");
}

//构造树pl为后序序列的左边界pr为其右边界  
//il为中续遍历的左边界ir为其右边界 
Tree *buildTree(int pl,int pr,int il,int ir)
{
    if (pl > pr)return NULL;
    int p = il;
    while (in[p] != pos[pr])
    {
        ++p;
    }
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->data = pos[pr];
    tree->le = buildTree(pl,pr-ir+p-1,il,p-1);
    tree->ri = buildTree(pr-ir+p,pr-1,p+1,ir);  

    return tree; 
}

int main(){  
    int n,i;  
    Tree *root;  

    scanf("%d",&n);  
    for(i=0;i<n;++i){  
        scanf("%d",&pos[i]);  
    }  
    for(i=0;i<n;++i){  
        scanf("%d",&in[i]);  
    }  
    root=buildTree(0,n-1,0,n-1);  
    printLevelOrder(root);  
    return 0;  
}

the main function is rebuild the tree,which is a recursive function;and it is important to find

the left side and the right side from both postOrder and InOrder!Therefore ,we can use these argument to build the tree recursively.