树的遍历

树的遍历

时间： 1ms        内存：128M

描述：

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入：

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

示例输入：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

示例输出：

4 1 6 3 5 7 2 

提示：

参考答案（内存最优[0]）：

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#define SizeMax 105  
using namespace std;  
typedef struct Node  
{  
    int data;  
    Node* lchild;  
    Node* rchild;  
} Node;  
Node *CreateBT2(int *post,int *in,int n)  
{  
    Node *b;  
    int r,*p,k;  
    if(n<=0)return NULL;  
    r=*(post+n-1);  
    b=(Node*)malloc(sizeof(Node));  
    b->data=r;  
    for(p=in; p<in+n; p++)  
        if(*p==r)break;  
    k=p-in;  
    b->lchild=CreateBT2(post,in,k);  
    b->rchild=CreateBT2(post+k,p+1,n-k-1);  
    return b;  
}  
void Print(Node *r)  
{  
    Node *p;  
    Node *pr[SizeMax];  
    int rear=-1,front=-1;  
    rear++;  
    pr[rear]=r;  
    while(rear!=front)  
    {  
        front=(front+1)%SizeMax;  
        p=pr[front];  
        printf("%d ",p->data);  
        if(p->lchild!=NULL)  
        {  
            rear=(rear+1)%SizeMax;  
            pr[rear]=p->lchild;  
        }  
        if(p->rchild!=NULL)  
        {  
            rear=(rear+1)%SizeMax;  
            pr[rear]=p->rchild;  
        }  
    }  
}  
int main()  
{  
    int N;  
    scanf("%d",&N);  
    int a[N],b[N];  
    for(int i=0; i<N; i++)  
        scanf("%d",a+i);  
    for(int i=0; i<N; i++)  
        scanf("%d",b+i);  
    Node* result=CreateBT2(a,b,N);  
    Print(result);  
    return 0;  
}  

参考答案（时间最优[0]）：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SizeMax 105
using namespace std;
typedef struct Node
{
    int data;
    Node* lchild;
    Node* rchild;
} Node;
Node *CreateBT2(int *post,int *in,int n)
{
    Node *b;
    int r,*p,k;
    if(n<=0)return NULL;
    r=*(post+n-1);
    b=(Node*)malloc(sizeof(Node));
    b->data=r;
    for(p=in; p<in+n; p++)
        if(*p==r)break;
    k=p-in;
    b->lchild=CreateBT2(post,in,k);
    b->rchild=CreateBT2(post+k,p+1,n-k-1);
    return b;
}
void Print(Node *r)
{
    Node *p;
    Node *pr[SizeMax];
    int rear=-1,front=-1;
    rear++;
    pr[rear]=r;
    while(rear!=front)
    {
        front=(front+1)%SizeMax;
        p=pr[front];
        printf("%d ",p->data);
        if(p->lchild!=NULL)
        {
            rear=(rear+1)%SizeMax;
            pr[rear]=p->lchild;
        }
        if(p->rchild!=NULL)
        {
            rear=(rear+1)%SizeMax;
            pr[rear]=p->rchild;
        }
    }
}
int main()
{
    int N;
    scanf("%d",&N);
    int a[N],b[N];
    for(int i=0; i<N; i++)
        scanf("%d",a+i);
    for(int i=0; i<N; i++)
        scanf("%d",b+i);
    Node* result=CreateBT2(a,b,N);
    Print(result);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。