题目如下：
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
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 postorder sequence and the third line gives the inorder sequence. All the numbers
in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. 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:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
这是一道很直接的给出中序序列和任一其他序列生成二叉树的问题，本题给出的是后序遍历和中序遍历，利用后序遍历的“左右根”顺序我们知道，后序序列的最后一个元素一定是整棵树的根，从后向前，分别是右、左子树的根，因此通过后序序列可以找到一系列的根，他们的顺序是当前所在的根、右子树的根、左子树的根，每次在中序序列中定位出根的位置，根据中序序列“左根右”的顺序我们知道，根左边的一定是左子树，右边的一定是右子树，就这样递归解决子树问题即可，最后通过BFS来进行层序遍历。
具体实现方法为，设中序序列为inOrder，后序序列为postOrder，设置一个游标变量cur，左右范围变量left、right，cur作为一个全局变量，每次在postOrder中取出一个根，就让cur自减1，首先把拿到的根定位在inOrder中，设根所在的索引为rootIndex，首先建立当前根节点T，然后生成左子树范围left到rootIndex-1和右子树范围rootIndex+1到right，注意由于后序序列倒着走线碰到右子树，因此应该先递归T->right，再递归T->left，当发现left比right大时，说明没有子树，直接返回NULL，当发现left=right时，说明这是一个叶子结点，将结点的left和right置为NULL然后返回，最后一次递归返回时返回的是第一次创建的根结点，也就是整棵树的根，这时便得到了完整的二叉树。
接下来要进行层序遍历，只要对二叉树从根开始调用BFS即可，在结点出队时进行输出。
#include <iostream>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue> using namespace std; #define MAX 40 int postOrder[MAX];
int inOrder[MAX];
int N;
int cur; typedef struct TreeNode *Tree;
struct TreeNode{ Tree left;
Tree right;
int num; }; int findRootIndex(int rootNum){ for(int i = 0;i < N; i++){
if(inOrder[i] == rootNum){
return i;
}
}
return -1; } Tree CreateTree(int left, int right){
if(left > right ) return NULL;
int root = postOrder[cur];
cur --;
int rootIndex = findRootIndex(root);
Tree T = (Tree)malloc(sizeof(struct TreeNode));
T->num = root;
if(left == right){
T->left = NULL;
T->right = NULL;
}else{
T->right = CreateTree(rootIndex+1,right);
T->left = CreateTree(left,rootIndex-1);
}
return T; } void BFS(Tree T){ bool firstout = true;
queue<Tree> q;
q.push(T); while(!q.empty()){ Tree t = q.front();
q.pop();
if(firstout){
firstout = false;
cout << t->num;
}else{
cout << " " << t->num;
}
if(t->left != NULL){
q.push(t->left);
}
if(t->right!= NULL){
q.push(t->right);
} } } int main()
{
cin >> N;
cur = N-1;
for(int i = 0; i < N; i++){
cin >> postOrder[i];
}
for(int i = 0; i < N; i++){
cin >> inOrder[i];
} Tree T = CreateTree(0,cur); BFS(T); cout << endl; return 0;
}