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 7Sample Output:
4 1 6 3 5 7 2
题意:根据题中所给出的后序遍历和中序遍历序列求树的层次遍历。
思路：先建立二叉树，再使用bfs就可以求解。
#include<iostream>
#include<queue>
using namespace std;
int postorder[40],inorder[40];
class Node
{
public:
int data;
Node *ld,*rd;
};
queue<Node*> st;
Node* CreateTree(int n,int *arry1,int *arry2)
{
if(n<=0) return NULL;
int k=0;
while(arry1[n-1]!=arry2[k])
k++;
Node *root=new Node;
root->data=arry1[n-1];
root->ld=CreateTree(k,arry1,arry2);
root->rd=CreateTree(n-k-1,arry1+k,arry2+k+1);
return root;
}
int main()
{
int n,i,j,k;
cin>>n;
for(i=0;i<n;i++)
cin>>postorder[i];
for(i=0;i<n;i++)
cin>>inorder[i];
Node *root=new Node;
root->ld=NULL;
root->rd=NULL;
root=CreateTree(n,postorder,inorder);
st.push(root);
//cout<<(st.back())->data<<endl;
int tag=0;
while(!st.empty())
{
if((st.front())->ld!=NULL) st.push((st.front())->ld);
if((st.front())->rd!=NULL) st.push((st.front())->rd);
if(tag==0) cout<<(st.front())->data,tag=1;
else cout<<" "<<(st.front())->data;
st.pop();
}
return 0;
}
[递归&&bfs]PAT1020 Tree Traversals
原文：http://blog.csdn.net/zju_ziqin/article/details/19752485