Advertisement
archit_jain

Untitled

Jun 25th, 2022
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None
  1.  
  2. TreeNode *pre(TreeNode *a){
  3.     if(a==NULL)return NULL;
  4.     TreeNode *ret = NULL;
  5.     TreeNode *t = a->left;
  6.     while(t!=NULL){
  7.         ret = t;
  8.         if(t->right == a)return ret;
  9.         t = t->right;
  10.     }
  11.     return ret;
  12. }
  13.  
  14. void morris(TreeNode *a,int &l, int &r){
  15.     if(a==NULL)return;
  16.     int last_printed = INT_MIN;
  17.     TreeNode *cur = a;
  18.     while(cur!=NULL){
  19.         if(cur->left==NULL){
  20.             // cout << cur->val << endl;
  21.             if(cur->val < last_printed){
  22.                 l = min(l,cur->val);
  23.                 r = max(r,last_printed);
  24.             }
  25.             last_printed = cur->val;
  26.             cur = cur->right;
  27.         }
  28.         else {
  29.             TreeNode *p = pre(cur);
  30.             if(p->right==NULL){
  31.                 p->right = cur;
  32.                 cur = cur->left;
  33.             }
  34.             else {
  35.                 p->right = NULL;
  36.                 // cout << cur->val << endl;
  37.                 if(cur->val < last_printed){
  38.                     l = min(l,cur->val);
  39.                     r = max(r,last_printed);
  40.                 }
  41.                 last_printed = cur->val;
  42.                 cur = cur->right;
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void trav(TreeNode *a,TreeNode *left,TreeNode *right, int &l, int &r){
  49.     if(!a)return;
  50.     if(left != NULL && left->val > a->val){
  51.         l = min(l,a->val);
  52.         r = max(r,left->val);
  53.     }
  54.     if(right != NULL && right->val < a->val){
  55.         l = min(l,right->val);
  56.         r = max(r,a->val);
  57.     }
  58.     trav(a->left,left,a,l,r);
  59.     trav(a->right,a,right,l,r);
  60. }
  61.  
  62. vector<int> Solution::recoverTree(TreeNode* a) {
  63.     // TreeNode *left = NULL, *right = NULL;
  64.     int l = INT_MAX,r = INT_MIN;
  65.     // trav(a,left,right,l,r);
  66.     morris(a,l,r);
  67.     return vector<int>{l,r};
  68. }
  69.  
  70.  
Advertisement
RAW Paste Data Copied
Advertisement