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 (≤), 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题意：
后序中序链表建树，求层序
AC代码：
#include<bits/stdc++.h> using namespace std; int n; struct node{ int data; node *left,*right; }; int post[35]; int in[35]; vector<int>level; queue<node*>q; node *build(int pl,int pr,int il,int ir){ if(pl>pr || il>ir) return NULL; int pos=-1; for(int i=il;i<=ir;i++){ if(in[i]==post[pr]){ pos=i; break; } } node *root=new node(); root->data=post[pr]; root->right=build(pr-(ir-pos),pr-1,pos+1,ir);//是ir-pos root->left=build(pl,pr-(ir-pos)-1,il,pos-1); return root; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>post[i]; for(int i=1;i<=n;i++) cin>>in[i]; node *root=build(1,n,1,n); q.push(root); while(!q.empty()){ root=q.front(); level.push_back(root->data); q.pop(); if(root->left) q.push(root->left); if(root->right) q.push(root->right); } for(int i=0;i<level.size();i++){ cout<<level.at(i); if(i!=level.size()-1) cout<<" "; } return 0; }