Guest User

Untitled

a guest
Aug 23rd, 2019
75
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