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 根据后序和中序遍历，建立二叉树之后输出层序遍历 #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> #include<algorithm> #include<cmath> using namespace std; typedef struct tree{ int num; struct tree *left; struct tree *right; }tree,*linktree; linktree creat(int *post,int *in,int num){ if(num<=0) return NULL; linktree lin=new tree; lin->num=post[num-1]; int index=0; for(int i=0;i<=num;i++){ if(in[i]==post[num-1]){ index=i; break; } } lin->left=creat(post,in,index); lin->right=creat(post+index,in+index+1,num-index-1); return lin; } void Traversals(linktree head){ queue<linktree> que; que.push(head); cout<<que.front()->num; while(que.size()){ if(que.front()->left){ que.push(que.front()->left); } if(que.front()->right){ que.push(que.front()->right); } que.pop(); if(que.size()) cout<<" "<<que.front()->num; } } int main(){ int post[100],in[100]; int n; cin>>n; for(int i=0;i<n;i++) cin>>post[i]; for(int i=0;i<n;i++) cin>>in[i]; linktree head=creat(post,in,n); Traversals(head); return 0; }
