morris

class Solution {

public:

TreeNode m1,m2,*prev;

void recoverTree(TreeNode* root) {

TreeNode p=root, temp;

//vector<int> ret;

while(p){

temp=p->left;

if(!temp){

inOrder(p);

p=p->right;

}

else{

while(temp->right!=nullptr && temp->right!=p)

temp=temp->right;

if(!temp->right){

temp->right=p;

p=p->left;

}else{

temp->right=nullptr;

inOrder(p);

p=p->right;

}

}

}

swap(m1->val,m2->val);

}

void inOrder(TreeNode* root){

if(prev&&prev->val>root->val){

if(!m1)

m1=prev;

m2=root;

}

prev=root;

}

};