1020. Tree Traversals (25)
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
这题也不难，由后序跟中序序列构建一颗树，然后以层次遍历的方法输出各节点数据，主要输出后要把树给销毁，不然会造成内存泄露。
代码
#include <stdio.h>
#include <stdlib.h> typedef struct Node{
int data;
struct Node *left,*right;
}Node;
int postOrder[];
int inOrder[];
Node* buildTree(int,int,int,int);
void printAndDestroyTree(Node *);
int main()
{
int N,i;
while(scanf("%d",&N) != EOF){
for(i=;i<N;++i){
scanf("%d",&postOrder[i]);
}
for(i=;i<N;++i){
scanf("%d",&inOrder[i]);
}
Node *tree = buildTree(,N-,,N-);
printAndDestroyTree(tree);
}
return ;
} Node* buildTree(int postStart,int postEnd,int inStart,int inEnd)
{
if(postStart == postEnd){
Node *p = (Node *)malloc(sizeof(Node));
p->data = postOrder[postStart];
p->left = p->right = NULL;
return p;
}
else{
Node *p = (Node *)malloc(sizeof(Node));
p->data = postOrder[postEnd];
p->left = p->right = NULL;
int i = inStart;
while(i<=inEnd && postOrder[postEnd] != inOrder[i++]);
if(i > inStart+)
p->left = buildTree(postStart,postStart+i-inStart-,inStart,i-);
if(i <= inEnd)
p->right = buildTree(postStart+i-inStart-,postEnd-,i,inEnd);
return p;
}
} void printAndDestroyTree(Node *p)
{
if(!p)
return;
Node *nodeArray[];
int top=,base=;
Node *q;
nodeArray[top++] = p;
while(top>base){
q = nodeArray[base++];
if(base == )
printf("%d",q->data);
else
printf(" %d",q->data);
if(q->left)
nodeArray[top++] = q->left;
if(q->right)
nodeArray[top++] = q->right;
free(q);
}
printf("\n");
}