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.
zigzag.jpg
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
这道题就是想根据前序和后序得到一棵树。
初次遇到，还是思考了挺长时间的，这里记录一下。
我的想法，包括很多思路是：每一层都用新的数组记录下来，输出的时候依次输出这些数组就行了。这里的话用结构体或者二维数组都可以，方便一点就用结构体了，可以记录下元素的个数。
关键在于两个数据。
可以看出，postorder的顺序
子树A子树B根但是子树的分界点未知。
inorder的顺序
子树A根子树B但是根是谁未知。
于是思路是：在postorder中找到最后一个元素，是根，然后根据根和inorder，再传进去两颗子树。
比较关键的是，同一颗子树，两个记录方式的位置是不同的，因此表示一颗子树，需要4个变量（可能可以更少，但是4个便于理解）子树在postorder开始/结束的位置，子树在inorder开始/结束的位置。
具体可以根据inorder中根左右两边的元素个数确定子树，然后算postorder中的位置。
比如根在post的位置是i,那么左边子树元素个数left=i-i1，右边子树元素的个数是right=j1-i
然后得到了inorder的子树A的位置：(i2,i2+left-1) 左边子树B的位置:(j2-right,right-1)
注意避开根，只传子树。当然right和left可以用另一个变量表示，这里是为了便于理解。
post 子树A的位置(i1,i-1),子树B的位置(i+1,j1)
注意当left和right不为0的时候，才需要算对应的子树，为0的时候说明左边或右边是NULL,不需要算。
然后传一个Level，下一层传level+1。
别看我说的麻烦，代码还是不长的，50行不到就可以，比网上大部分的少。
