内存:128  时间:1

题目描述

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

输入

输入第一行给出一个正整数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

提示

 若不存在这样的序列,则什么也不输出

代码如下

#include<iostream>
#include<malloc.h>
#define maxn 100
using namespace std;
typedef struct Node {
	int data;
	Node * lchild;
	Node * rchild;
}Node ;
Node * Creat(int *post,int *in,int n)
{
  if(n<=0) return NULL;
  Node * b;
  int r,*p,k;
  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=Creat(post,in,k);
  b->rchild=Creat(post+k,p+1,n-k-1);
  return b;	
}
void print(Node * res)  //利用队列以层次遍历的方式输出 
{
	Node * p;
	Node * sta[maxn];
   int head;
   int tail;
   head=0;
   tail=1;
   sta[1]=res;//根节点入栈! 
   while(head<tail)
   {
     cout<<sta[++head]->data<<" ";
	 if(sta[head]->lchild!=NULL)
	 {
	 	sta[++tail]=sta[head]->lchild;
	    	
	 }  
	if(sta[head]->rchild!=NULL)
	 {
	 	sta[++tail]=sta[head]->rchild;	
	 } 	
   } 
}
int main(void)
{
	int n;
	cin>>n;
	int a[n];	   //后序 
	int 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 * res=Creat(a,b,n);
	print(res);
 } 

代码来源于互联网,仅供参考!