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分析： 利用后序，中序转层序，并用map记录节点 输出的时候用二维数据v记录，（i=1…k）当第i行能被2整除是从左到右依次输出，否则从右到左输出。
代码：
#include<iostream> #include<map> #include<cmath> #include<vector> using namespace std; int n; int post[31]; int in[31]; std::map<int, int> tree; void level(int root ,int left,int right,int depth){ if(left>right) return; tree[depth] = post[root]; int i = 0; for (i = left; i <= right; ++i) { if(post[root] == in[i]){ break; } } level(root-1-(right - i),left,i-1,2*depth+1); level(root-1,i+1,right,2*depth+2); } int main(int argc, char const *argv[]) { cin>>n; for (int i = 0; i < n; ++i) { cin>>in[i]; } for (int i = 0; i < n; ++i) { cin>>post[i]; } level(n-1,0,n-1,0); std::vector<int> v[100]; int k = 1; std::map<int, int> ::iterator it; for(it = tree.begin();it !=tree.end();it++){ //cout<<it->first<<' '; if((it->first)<=(pow(2,k)-2)){ //cout<<k<<' '<<it->second<<endl; v[k].push_back(it->second); }else{ k++; //cout<<k<<' '<<it->second<<endl; v[k].push_back(it->second); } } cout<<v[1][0]; for (int i = 2; i <= k; ++i) { if(i%2 == 1){ for (int j = v[i].size()-1; j>=0 ;j--) { cout<<' '<<v[i][j]; } }else{ for (int j = 0; j < v[i].size(); ++j) { cout<<' '<<v[i][j]; } } } return 0; }二叉树( Binary Tree)是n(n≥0)个结点的有限集合，该集合 或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交 的、分别称为根结点的左子树和右子树的二叉树组成。
满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上（最后一层）。 所以，满二叉树非叶子结点度一定是2，叶子数最多
完全二叉树 (1)叶子结点只能出现在最下两层。 (2)最下层的叶子一-定集中在左部连续位置。 (3)倒数二层，若有叶子结点，一定都在右部连续位置。 (4)如果结点度为1,则该结点只有左孩子，即不存在只有右子树的情况。 (5)同样结点数的二叉树，完全二叉树的深度最小。
1）第i层上最多有2^{i-1}个结点 2）深度为k的二叉树至多有2^k -1个节点 3）对于任何一棵二叉树T，叶子节点数为n0,度为2的节点数为n2,则n0=n2+1 4）n个节点的完全二叉树深度为[log2n]+1 5)如果对棵有n个结点的完全二叉树,对任-结点i (1<i<n) 有: 1.如果i=1,则结点i是二叉树的根，无双亲;如果i>1, 则其双亲是结点 [I/2]。 2.如果2i>n, 则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i 3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。
