PAT-A 1020 Tree Traversals (25 分)

PAT-A 1020 Tree Traversals (25 分)

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式
第一行包含整数 N，表示二叉树的节点数。

第二行包含 N 个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式
输出一行 N 个整数，表示二叉树的层序遍历。

数据范围
1≤N≤30
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

经典的建树问题与层序遍历

#include 

using namespace std;
struct node
{
    int data;
    struct node*l,*r;
};
int n;
int num=0;
const int N  = 33;
int inorder[N],postorder[N];
struct node*create(int h1,int h2,int len)//中起始下标、后起始下标、长度
{
    if(len==0)
    return NULL;
    struct node*p ;
    p=new node;
    p->data=postorder[h2+len-1];
    int i;
    for( i=h1;inorder[i]!=postorder[h2+len-1];i++);
    int l1 = i-h1;
    int l2 = len-1-l1;
    p->l = create(h1,h2,l1);
    p->r = create(i+1,h2+l1,l2);
    return p;
};
void level(struct node *&tree)
{
    queueq;
    q.push(tree);
    while(!q.empty())
    {
        node *now = q.front();
        q.pop();
        num++;
        cout <data;
        if(num!=n)
        cout <<" ";
        if(now->l)
        q.push(now->l);
        if(now->r)
        q.push(now->r);
    }
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    cin >>postorder[i];
    for(int i=1;i<=n;i++)
    cin >>inorder[i];
    struct node *root = create(1,1,n);
    
    level(root);
    
    
    return 0;
}