学步园

告诉二叉树的前序遍历和中序遍历，来恢复二叉树，并输出后序遍历的结果。

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

struct node
{
    int val;
    node *ch[2];
};

int Search(int x,int A[],int n)
{
    for(int i=0;i<n;i++)
       if(x == A[i])
           return i;
    return 0;
}

node *Restore(int A[],int B[],int n)
{
    if(n<=0) return NULL;
    node *p = new node();
    p->val = *A;
    p->ch[0] = p->ch[1] = NULL;
    int i = Search(*A,B,n);
    int *r = B + i;
    int j = r - B;
    p->ch[0] = Restore(A+1,B,j);
    p->ch[1] = Restore(A+1+j,r+1,n-1-j);
    return p;
}

void Postorder(node *t)
{
    if(t == NULL) return;
    Postorder(t->ch[0]);
    Postorder(t->ch[1]);
    printf("%d ",t->val);
}

int main()
{
    int n;
    int A[55],B[55]; //数组A和B分别表示前序遍历的序列和后序遍历的序列
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
            cin>>A[i];
        for(int i=0;i<n;i++)
            cin>>B[i];
        node *root = Restore(A,B,n);   //恢复二叉树
        Postorder(root);
        cout<<endl;
    }
    return 0;
}