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:

812 11 20 17 1 15 8 512 20 17 11 15 8 5 1

Sample Output:

1 11 5 8 17 12 20 15 首先通过后续遍历和中序遍历重构二叉树 然后在层序遍历的基础上，进行元素逆序

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 struct Node 7 { 8     int v; 9     Node *l, *r;10     Node(int a = -1) :v(a), l(nullptr), r(nullptr) {}11 };12 int n;13 vector
         
          inOrder, posOrder, zigOrder;14 Node* reCreatTree(int inL, int inR, int posL, int posR)15 {16     if (posL > posR)17         return nullptr;18     Node* root = new Node(posOrder[posR]);19     int k = inL;20     while (k<=inR && inOrder[k] != posOrder[posR])++k;//找到根节点21     int numL = k - inL;//左子树节点个数22     root->l = reCreatTree(inL, k - 1, posL, posL + numL - 1);23     root->r = reCreatTree(k + 1, inR, posL + numL, posR - 1);24     return root;25 }26 void zigOrderTravel(Node* root)27 {28     if (root == nullptr)29         return;30     queue
          
           q;31 q.push(root);32 zigOrder.push_back(root->v);33 bool flag = false;34 while (!q.empty())35 {36 queue
           
            temp;37 vector
            
             tt;38 while (!q.empty())39 {40 Node* p = q.front();41 q.pop();42 if (p->l != nullptr)43 {44 temp.push(p->l);45 tt.push_back(p->l->v);46 }47 if (p->r != nullptr)48 {49 temp.push(p->r);50 tt.push_back(p->r->v);51 }52 }53 if (flag)54 reverse(tt.begin(), tt.end());55 zigOrder.insert(zigOrder.end(), tt.begin(), tt.end());56 flag = !flag;57 q = temp;58 }59 }60 int main()61 {62 cin >> n;63 inOrder.resize(n);64 posOrder.resize(n);65 for (int i = 0; i < n; ++i)66 cin >> inOrder[i];67 for (int i = 0; i < n; ++i)68 cin >> posOrder[i];69 Node* root = reCreatTree(0, n - 1, 0, n - 1);70 zigOrderTravel(root);71 for (int i = 0; i < zigOrder.size(); ++i)72 cout << (i > 0 ? " " : "") << zigOrder[i];73 return 0;74 }