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:72 3 1 5 7 6 41 2 3 4 5 6 7Sample Output:
4 1 6 3 5 7 2
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>using namespace std;#define N 3005struct node{int l,r;}a[N];int post[35],in[35];int gettree(int lp,int rp,int li,int ri){if(lp>=rp)return -1;int i,x=post[rp-1];for(i=li;i<ri;i++)if(in[i]==x)break;a[x].l=gettree(lp,rp-ri+i,li,i);a[x].r=gettree(rp-ri+i,rp-1,i+1,ri);return x;}int main(){int n,i,root,x,ans;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&post[i]);for(i=0;i<n;i++)scanf("%d",&in[i]);root=gettree(0,n,0,n);queue<int>que;que.push(root);ans=0;while(que.size()){x=que.front();if(!ans){printf("%d",x);ans=1;}elseprintf(" %d",x);if(a[x].l!=-1)que.push(a[x].l);if(a[x].r!=-1)que.push(a[x].r);que.pop();}printf("\n");}return 0;}
，我想，这就是旅行的真义吧。
