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 7

Sample Output:

4 1 6 3 5 7 2

---

编译器

Assembler (nasm)Basic (blassic)C (gcc)C# (gmcs)C++ (g++)Go (gccgo)Haskell (ghc)Java (java)Javascript (js)Lisp (clisp)Lua (lua)Pascal (fpc)Perl (perl)PHP (php)Plaintext (cat)Python (python3)Python (python2)Ruby (ruby)Scheme (guile)Shell (bash)Vala (valac)VisualBasic (vbnc)

 

代码

#include <map> #include <string> #include<algorithm> #include <iostream> #include<queue> using namespace std; int postorder[35]; int inorder[35]; int m; typedef struct tn { struct tn* letf; struct tn* right; int value; }treenode; queue<treenode *> qu; treenode * createtree(int pl,int pr,int il,int ir) { int p; treenode * tt=new treenode; if(ir<il||pr<pl)return NULL; /* else if(ir==il) { tt->value =inorder[ir]; // printf("%d ",tt->value); tt->letf=tt->right=NULL; return tt; }*/ else { tt->value=postorder[pr]; // printf("%d ",tt->value); for(p=il;p<m;p++) if(inorder[p]==postorder[pr]) break; // printf("*%d*",p); tt->letf=createtree(pl,pl+p-il-1,il,p-1); tt->right=createtree(pl+p-il,pr-1,p+1,ir); } return tt; } void levelorder(treenode* t) { treenode* ttt; int first=1; if(t!=NULL) qu.push(t); while(!qu.empty()) { ttt=qu.front (); qu.pop(); if(first) first=0; else printf(" "); printf("%d",ttt->value); if(ttt->letf!=NULL) qu.push (ttt->letf); if(ttt->right!=NULL) qu.push (ttt->right); } } int main() { // freopen("data.in","r",stdin); int n,i,j,k; scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d",&postorder[i]); } for(i=0;i<m;i++) scanf("%d",&inorder[i]); treenode* root; root=createtree(0,m-1,0,m-1); levelorder(root); return 0; }

#include 
      
       #include
       
        #include 
        
         #include
         
          using namespace std;int postorder[35];int inorder[35];int m;typedef struct tn{	struct tn* letf;	struct tn* right;	int value;}treenode;queue
          
            qu;treenode * createtree(int pl,int pr,int il,int ir){	int p;	treenode * tt=new treenode;	if(ir
           
            
             value=postorder[pr];// printf("%d ",tt->value); for(p=il;p
             
              letf=createtree(pl,pl+p-il-1,il,p-1); tt->right=createtree(pl+p-il,pr-1,p+1,ir); } return tt;} void levelorder(treenode* t){ treenode* ttt; int first=1; if(t!=NULL) qu.push(t); while(!qu.empty()) { ttt=qu.front (); qu.pop(); if(first) first=0; else printf(" "); printf("%d",ttt->value); if(ttt->letf!=NULL) qu.push (ttt->letf); if(ttt->right!=NULL) qu.push (ttt->right); }}int main(){ freopen("data.in","r",stdin); int n,i,j,k; scanf("%d",&m); for(i=0;i
             
            
           
          
         
        
       
      

　　

---