7-9 还原二叉树
分数 10
作者 王云武
单位 浙大城市学院
给出一颗二叉树的中序遍历和后序遍历，请你实现以下两个需求：
（1）请你输出这颗二叉树的层序遍历。
（2）请你输出这颗二叉树的树高。
输入格式:
第一行包含一个整数N（N<=1000）。二叉树的节点将从1到N编号。
第二行包含N个节点编号，表示这颗二叉树的中序遍历。
第三行包含N个节点编号，表示这颗二叉树的后序遍历。
输出格式:
第一行输出二叉树的层序遍历，节点编号之间用空格分隔，末尾没有多余空格。
第二行输出一个整数，代表二叉树的树高。
题目不保证输入的序列合法，如果遇到不合法的情况，请在一行中输出"ERROR"，直接退出程序。
输入样例:
在这里给出一组输入。例如：
6
6 5 4 3 2 1
5 6 2 3 1 4
输出样例:
在这里给出相应的输出。例如：
4 6 1 5 3 2
4
输入样例:
在这里给出一组输入。例如：
3
2 1 3
3 2 1
输出样例:
在这里给出相应的输出。例如：
ERROR
#include <iostream>
using namespace std;
#define MAX 100000
typedef struct Tnode
{
int data;
Tnode *lchild, *rchild;
}Tnode, *Tree;
typedef struct
{
Tree *base;
int front;
int rear;
}Queue;
int treehigh ( Tree T )
{
if ( T == NULL )
{
return 0;
}
int len1 = treehigh (T->lchild);
int len2 = treehigh (T->rchild);
return len1 > len2 ? len1+1:len2+1;
}
void creat ( Tree &T, int *in, int *post, int n)
{
T = new Tnode;
if ( n == 0 )
{
return;
}
int i;
T->data = post[n-1];
for ( i = 0; i < n; i ++ )
{
if ( in[i] == T->data )
{
break;
}
}
creat (T->lchild, in, post, i);
creat (T->rchild, in+i+1, post+i, n-i-1);
}
void init ( Queue &Q )
{
Q.base = new Tree[MAX];
Q.front = Q.rear = 0;
}
void enqueue ( Queue &Q, Tree e )
{
Q.base[Q.rear] = e;
Q.rear = Q.rear+1;
}
void dequeue( Queue &Q, Tree &p )
{
if ( Q.front == Q.rear )
{
return;
}
p = Q.base[Q.front];
Q.front = Q.front + 1;
}
void LevelOrder( Tree &T, Queue &Q, int n )
{
int cnt = n;
Tree p;
p = new Tnode;
enqueue (Q, T);
while ( Q.front != Q.rear )
{
dequeue (Q, p);
if ( p->data != 0 )
{
cout << p->data;
if ( cnt > 1 )
{
cout << " ";
}
cnt --;
}
if ( p->lchild != NULL )
{
enqueue (Q, p->lchild);
}
if ( p->rchild != NULL )
{
enqueue(Q, p->rchild);
}
}
}
int main ()
{
Tree T;
int n;
cin >> n;
int a[n], b[n];
for ( int i = 0; i < n; i ++ )
{
cin >> a[i];
}
for ( int i = 0; i < n; i ++ )
{
cin >> b[i];
}
int *in = a;
int *post = b;
creat (T, in, post, n);
Queue Q;
init (Q);
LevelOrder (T, Q, n);
cout <<endl;
int high = treehigh (T);
cout << high-1<<endl;
}
