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:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
Sample Output:
1 11 5 8 17 12 20 15题意：中序和后序建树，然后按zigzagging order输出。
分析：层序遍历的时候将节点输出到容器中，最后输出的时候根据奇数还是偶数来输出结点
/**
* Copyright(c)
* All rights reserved.
* Author : Mered1th
* Date : 2019-02-28-14.24.50
* Description : A1127
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
;
int n,post[maxn],in[maxn];
vector<int> ans[maxn];
struct Node{
int val,layer;
Node* lchild;
Node* rchild;
Node(int _val,int _layer){
val=_val;
lchild=NULL;
rchild=NULL;
layer=_layer;
}
};
;
Node* create(int inL,int inR,int postL,int postR,int layer){
if(inL>inR) return NULL;
if(layer>maxlayer) maxlayer=layer;
int rootVal=post[postR];
Node* root=new Node(rootVal,layer);
int k;
for(int i=inL;i<=inR;i++){
if(post[postR]==in[i]){
k=i;
break;
}
}
int numLeft=k-inL;
root->lchild=create(inL,k-,postL,postL+numLeft-,layer+);
root->rchild=create(k+,inR,postL+numLeft,postR-,layer+);
return root;
}
void BFS(Node* root){
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node* now=q.front();
q.pop();
ans[now->layer].push_back(now->val);
if(now->lchild!=NULL) q.push(now->lchild);
if(now->rchild!=NULL) q.push(now->rchild);
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d",&n);
;i<n;i++){
scanf("%d",&in[i]);
}
;i<n;i++){
scanf("%d",&post[i]);
}
Node* root=create(,n-,,n-,);
BFS(root);
;i<=maxlayer;i++){
){
printf(]);
continue;
}
==){
;j<ans[i].size();j++){
printf(" %d",ans[i][j]);
}
}
else{
;j>=;j--){
printf(" %d",ans[i][j]);
}
}
}
;
}