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.
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
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include<iostream> #include<queue> #include<stack> using namespace std; int n; int postorder[31],inorder[31]; 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<node *> Q; Q.push(ROOT); while(!Q.empty()){ node * cur=Q.front(); Q.pop(); if(cur==NULL||cur->data==-1)continue; cout<<cur->data<<" "; Q.push(cur->left); Q.push(cur->right); } } void ZigZagging_Order(node * ROOT){ deque<node *> Q; deque<node *> 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<<cur->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<<cur->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); } |