# 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.

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


 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 #include #include #include using namespace std; int n; int postorder,inorder; struct node{     int data;     node * left;     node * right; }; void MakeTree(int post_start,int post_end,int in_start,int in_end,node * CURRENT){     CURRENT->data=postorder[post_end];     if(post_start>post_end||in_start>in_end){         CURRENT->data=-1;         CURRENT->left=NULL;         CURRENT->right=NULL;         return;     }     else if(post_start==post_end&&in_start==in_end){         CURRENT->left=NULL;         CURRENT->right=NULL;         return;     }     node * left=new node;     node * right=new node;     CURRENT->left=left;     CURRENT->right=right;     int pos;     for(int i=in_start;i<=in_end;i++){         if(inorder[i]==postorder[post_end]){             pos=i;             break;         }     }     MakeTree(post_start,post_start+pos-1-in_start,in_start,pos-1,left);     MakeTree(post_start+pos-in_start,post_end-1,pos+1,in_end,right); } void level_Order(node * ROOT){     queue Q;     Q.push(ROOT);     while(!Q.empty()){         node * cur=Q.front();         Q.pop();         if(cur==NULL||cur->data==-1)continue;         cout<data<<" ";         Q.push(cur->left);         Q.push(cur->right);     } } void ZigZagging_Order(node * ROOT){     deque Q;     deque S;     bool first=true;     S.push_front(ROOT);     bool flag=false;//true为队列，false为栈     while(!(Q.empty()&&S.empty())){         node * cur;         if(flag==true){//队列             cur=Q.front();             Q.pop_front();             if(!first){                 cout<<" ";             }else{                 first=false;             }             cout<data;             if(cur->left!=NULL&&cur->left->data!=-1)S.push_front(cur->left);             if(cur->right!=NULL&&cur->right->data!=-1)S.push_front(cur->right);             if(Q.empty())flag=false;         }else{//栈             cur=S.front();             S.pop_front();             if(!first){                 cout<<" ";             }else{                 first=false;             }             cout<data;             if(cur->left!=NULL&&cur->right->data!=-1)Q.push_front(cur->right);             if(cur->right!=NULL&&cur->left->data!=-1)Q.push_front(cur->left);             if(S.empty())flag=true;         }     } } int main(){     ios::sync_with_stdio(false);     cin>>n;     for(int i=1;i<=n;i++){         cin>>inorder[i];     }     for(int i=1;i<=n;i++){         cin>>postorder[i];     }     node * ROOT=new node;     MakeTree(1,n,1,n,ROOT);     ZigZagging_Order(ROOT); }