SHARE
TWEET

Untitled

a guest Aug 23rd, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<cstdio>
  2. #include<queue>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 30;
  7.  
  8. struct Node{
  9.     int data;
  10.     Node* left;
  11.     Node* right;
  12. };
  13.  
  14. int post[MAXN];
  15. int in[MAXN];
  16. int n;
  17.  
  18. Node* reconstruct(int post_left, int post_right, int in_left, int in_right){
  19.     if(post_left>post_right) return NULL;
  20.     Node* root = new Node;
  21.     root->data = post[post_right];
  22.     int k = in_left;
  23.     for(;k<=in_right;k++){
  24.         if(in[k]==post[post_right]) break;
  25.     }
  26.     int num = k-in_left;
  27.     root->left = reconstruct(post_left, post_left+num-1, in_left, k-1);
  28.     root->right = reconstruct(post_left+num, post_right-1, k+1, in_right);
  29.     return root;
  30. }
  31.  
  32. void layerOrder(Node* root){
  33.     queue<Node*> q;
  34.     q.push(root);
  35.     int i=0;
  36.     while(!q.empty()){
  37.         Node* now = q.front();
  38.         q.pop();
  39.         i++;               
  40.         printf("%d", now->data);
  41.         if(i<n) printf(" ");
  42.         if(now->left!=NULL) q.push(now->left);
  43.         if(now->right!=NULL) q.push(now->right);
  44.     }
  45.     printf("\n");
  46. }
  47. int main(){
  48.     freopen("in.txt", "r", stdin);
  49.    
  50.     scanf("%d", &n);
  51.     for(int i=0;i<n;i++) scanf("%d", &post[i]);
  52.     for(int i=0;i<n;i++) scanf("%d", &in[i]);
  53.    
  54.     Node* root = reconstruct(0, n-1, 0, n-1);
  55.     layerOrder(root);
  56.     return 0;
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top