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
思路：
由后序和中序即可唯一确定一棵树。树结构采用顺序结构，Tree[i]中存放i结点的左右孩子下标（空则为-1）.
每次递归调用，找出后序遍历序列的最后一个元素，该元素即为该子树的根节点，随后在中序序列找到该元素下标，从而确定根节点左右子树序列长度，递归遍历左右子树。边递归边建树。最后层序遍历即可。
源码：
#include<bits/stdc++.h>
#define Max 31
using namespace std;
int post[Max];
int in[Max];
vector<int> Tree[Max];
int Tree_travel(const int* post,const int* in,int length)
{
if(length==0)
return -1;
int t=*(post+length-1);
int i;
for(i=0;i<length;i++)
{
//找到根节点在中序序列中的下标i
if(in[i]==t)
break;
}
//递归遍历左右子树，找出左右子树根节点
int left=Tree_travel(post,in,i);
int right=Tree_travel(post+i,in+i+1,length-i-1);
//建树
Tree[t].push_back(left);
Tree[t].push_back(right);
return t;
}
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
cin>>post[i];
for(int i=0;i<n;i++)
cin>>in[i];
int root=Tree_travel(post,in,n);
cout<<root;
//层序遍历
queue<int> que;
que.push(Tree[root][0]);
que.push(Tree[root][1]);
while(!que.empty())
{
int t=que.front();
que.pop();
if(t!=-1)
{
cout<<" "<<t;
que.push(Tree[t][0]);
que.push(Tree[t][1]);
}
}
}