Recursive

class Solution {

public:

TreeNode p,q,*prev;

void recoverTree(TreeNode* root) {

inOrder(root);

swap(p->val,q->val);

}

void inOrder(TreeNode* root){

if(root->left) inOrder(root->left);

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

if(!p)

p=prev;

q=root;

}

prev=root;

if(root->right) inOrder(root->right);

}

};