1127 ZigZagging on a Tree (30分)
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.
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.
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.
8 12 11 20 17 1 15 8 5 12 20 17 11 15 8 5 1
1 11 5 8 17 12 20 15
题意：给定一棵二叉树的中序遍历序列和后序遍历序列，要求层序输出“zigzagging”层序遍历序列，即第2n层（根节点在第一层）从左往右输出结点信息，第2n+1层从右往左输出结点信息。
思路：中序-后序序列建立二叉树，在建树的时候给定每个结点所在层数，使用两种层序遍历遍历二叉树，一种先从左往右（所用队列记作q1），另一种从右往左(所用队列记作q2)，判断当前要遍历的结点所在的层数，在2n层则输出q1中pop出来的结点信息，反之输出q2pop出来的结点信息。
1 #include<cstdio> 2 #include<stdlib.h> 3 #include<queue> 4 using namespace std; 5 int in[35],post[35]; 6 int n; 7 typedef struct node{ 8 int id; 9 node* left; 10 node* right; 11 int layer; 12 }node; 13 void levelOrder(node* root){ 14 queue<node*> q1,q2; 15 q1.push(root); 16 q2.push(root); 17 int i=1; 18 int cnt=0; 19 while(!q1.empty()){ 20 node* v1=q1.front(); 21 node* v2=q2.front(); 22 q1.pop(); 23 q2.pop(); 24 if(v1->layer%2==1){ 25 if(cnt!=n-1) 26 printf("%d ",v1->id); 27 else 28 printf("%d",v1->id); 29 cnt++; 30 } 31 else{ 32 if(cnt!=n-1) 33 printf("%d ",v2->id); 34 else 35 printf("%d",v2->id); 36 cnt++; 37 } 38 39 if(v1->left!=NULL) 40 q1.push(v1->left); 41 if(v1->right!=NULL) 42 q1.push(v1->right); 43 if(v2->right!=NULL) 44 q2.push(v2->right); 45 if(v2->left!=NULL) 46 q2.push(v2->left); 47 48 i*=-1; 49 } 50 51 } 52 node* buildTree(int inL,int inR,int postL,int postR,int layer){ 53 if(inL>inR||postL>postR) 54 return NULL; 55 int v=post[postR]; 56 int x=inL; 57 while(in[x]!=v&&x<=inR){ 58 x++; 59 } 60 node* root=(node*)malloc(sizeof(node)); 61 root->id=in[x]; 62 root->layer=layer; 63 root->left=buildTree(inL,x-1,postL,postL+x-inL-1,layer+1); 64 root->right=buildTree(x+1,inR,postL+x-inL,postR-1,layer+1); 65 return root; 66 } 67 int main(){ 68 69 scanf("%d",&n); 70 for(int i=0;i<n;i++){ 71 scanf("%d",&in[i]); 72 } 73 for(int i=0;i<n;i++){ 74 scanf("%d",&post[i]); 75 } 76 node* root=buildTree(0,n-1,0,n-1,0); 77 levelOrder(root); 78 return 0; 79 }
原文：https://www.cnblogs.com/foodie-nils/p/13141269.html