PATA1127 Zigzagging on a Tree

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

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 inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. 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:

1
2
3
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output:

1
1 11 5 8 17 12 20 15

题目大意:
给出中序遍历和后序遍历序列,求zigzagging遍历序列,即奇数层顺序输出,偶数层逆序输出(设根结点为第0层)
思路:
结合二叉树及其基本操作中给出的由先序中序构造二叉树的方法,类比写出此题的二叉树构造函数create(),而后进行层序遍历,开辟数组vector ans[]用于在遍历过程中将同一层的结点data值push入对应层号的数组,以便在输出时按层号进行顺逆序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
struct node{
int data,layer;
node* lchild;
node* rchild;
};
int in[35],post[35];
node* create(int inL,int inR,int postL,int postR){
if(postL>postR) return NULL;
node* root=new node;
root->data=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR])
break;
}
int numL=k-inL;
root->lchild=create(inL,k-1,postL,postL+numL-1);
root->rchild=create(k+1,inR,postL+numL,postR-1);
return root;
}
vector<int> ans[35];
void bfs(node* root){
queue<node*> q;
root->layer=0;
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
ans[now->layer].push_back(now->data);
if(now->lchild!=NULL){
now->lchild->layer=now->layer+1;
q.push(now->lchild);
}
if(now->rchild!=NULL){
now->rchild->layer=now->layer+1;
q.push(now->rchild);
}
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&in[i]);
for(int i=0;i<n;i++)
scanf("%d",&post[i]);
node* root=create(0,n-1,0,n-1);
bfs(root);
printf("%d",ans[0][0]);
for(int i=1;i<35;i++){
if(i%2==1){
for(int j=0;j<ans[i].size();j++)
printf(" %d",ans[i][j]);
}else{
for(int j=ans[i].size()-1;j>=0;j--)
printf(" %d",ans[i][j]);
}
}
return 0;
}

【最爱的还是柳婼小姐姐的代码,精简又高效,全网一级棒PAT1127liuchuo