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.

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.

812 11 20 17 1 15 8 512 20 17 11 15 8 5 1Sample Output:
1 11 5 8 17 12 20 15
#include<cstdio>#include<queue>#include<vector>#include<algorithm>using namespace std;int vert;//节点数vector<int> in,post,level[32];struct Node{int val,lel;Node *lchild,*rchild;Node():lchild(NULL),rchild(NULL){}};//struct类型后面记得加分号int maxlel = -1;Node* create(int inl,int inr,int pl,int pr,int lel){//创建树的同时将每层的结点加入到容器中if(inl>inr || pl>pr)return NULL;Node *root = new Node();//申请新结点root->val = post[pr];root->lel = lel;maxlel = max(lel,maxlel);level[lel].push_back(root->val);int k;for(k = inl;k<=inr;k++)if(in[k] == post[pr])break;int rlen = inr-k;root->lchild = create(inl,k-1,pl,pr-rlen-1,lel+1);root->rchild = create(k+1,inr,pr-rlen,pr-1,lel+1);return root;}int main(void){scanf("%d",&vert);in.resize(vert);post.resize(vert);for(int i = 0;i<vert;i++)scanf("%d",&in[i]);for(int i = 0;i<vert;i++)scanf("%d",&post[i]);Node *root = NULL;root = create(0,vert-1,0,vert-1,0);printf("%d",level[0][0]);for(int i = 1;i<=maxlel;i++){if(i%2==0)for(int j = level[i].size()-1;j>=0;j--)printf(" %d",level[i][j]);elsefor(int j = 0;j<level[i].size();j++)printf(" %d",level[i][j]);}}