真二叉树重构(Proper Rebuild)

Description

In general, given the preorder traversal sequence and postorder traversal sequence of a binary tree, we cannot determine the binary tree.

Figure 1

In Figure 1 for example, although they are two different binary tree, their preorder traversal sequence and postorder traversal sequence are both of the same.

But for one proper binary tree, in which each internal node has two sons, we can uniquely determine it through its given preorder traversal sequence and postorder traversal sequence.

Label n nodes in one binary tree using the integers in [1, n], we would like to output the inorder traversal sequence of a binary tree through its preorder and postorder traversal sequence.

Input

The 1st line is an integer n, i.e., the number of nodes in one given binary tree,

The 2nd and 3rd lines are the given preorder and postorder traversal sequence respectively.

Output

The inorder traversal sequence of the given binary tree in one line.

Input

5
1 2 4 5 3
4 5 2 3 1

Output

4 2 5 1 3

Restrictions

For 95% of the estimation, 1 <= n <= 1,000,00

For 100% of the estimation, 1 <= n <= 4,000,000

The input sequence is a permutation of {1,2...n}, corresponding to a legal binary tree.

Time: 2 sec

Memory: 256 MB

Hints

Figure 2

In Figure 2, observe the positions of the left and right children in preorder and postorder traversal sequence.

（图一）

提示

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 #include using namespace std; int n; int * preorder; int * postorder; bool first_output; struct node{     int data;     node * left;     node * right; }; int findpos(int * ptr_to_array,int value,int start,int end){ //[start,end]     for(int i=start;i<=end;i++){         if(ptr_to_array[i]==value)return i;     }     return -1; } bool MakeTree(int pre_start,int pre_end,int post_start,int post_end,node * CURRENT){// preorder[pre_start,pre_end];postorder[post_start,post_end]     if(pre_start>pre_end||post_start>post_end){         return false;     }     int V,L,R;     V=preorder[pre_start];     CURRENT->data=V;     if(pre_start==pre_end&&post_start==post_end){         CURRENT->left=NULL;         CURRENT->right=NULL;         return true;     }     L=preorder[pre_start+1];     R=postorder[post_end-1];     int L_pos_in_postorder=findpos(postorder,L,post_start,post_end);     int R_pos_in_preorder=findpos(preorder,R,pre_start,pre_end);     node * left=new node;     node * right=new node;     CURRENT->left=left;     CURRENT->right=right;     bool lflag=MakeTree(pre_start+1,R_pos_in_preorder-1,post_start,L_pos_in_postorder,left);     bool rflag=MakeTree(R_pos_in_preorder,pre_end,L_pos_in_postorder+1,post_end-1,right);     if(!lflag){         delete left;         CURRENT->left=NULL;     }     if(!rflag){         delete right;         CURRENT->right=NULL;     }     return true; } void Inorder_traversal(node * ptr){     if(ptr==NULL)return;     Inorder_traversal(ptr->left);     if(first_output){         cout<data;         first_output=false;     }else{         cout<<" "<data;     }     Inorder_traversal(ptr->right); } int main(){     first_output=true;     ios::sync_with_stdio(false);     cin>>n;     preorder=new int[n+1];     postorder=new int[n+1];     for(int i=1;i<=n;i++){         cin>>preorder[i];     }     for(int i=1;i<=n;i++){         cin>>postorder[i];     }     node * ROOT=new node;     MakeTree(1,n,1,n,ROOT);     Inorder_traversal(ROOT); }