/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void swap(int& a,int&b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
    TreeNode* findlarge(TreeNode* root,int val)
    {
        if(root==NULL) return NULL;
        TreeNode* result=NULL;
        if(root->val>val) 
        {
            val=root->val;
            result=root;
        }
        TreeNode* p1=findlarge(root->left,val);
        TreeNode* p2=findlarge(root->right,val);
        if(p1!=NULL) result=p1;
        if(p2!=NULL)
        {
            if(result==NULL) result=p2;
            else 
                if(result->val<p2->val) result=p2;
        }
        return result;
    }    
    TreeNode* findsmall(TreeNode* root,int val)
    {
        if(root==NULL) return NULL;
        TreeNode* result=NULL;
        if(root->val<val) 
        {
            val=root->val;
            result=root;
        }
        TreeNode* p1=findsmall(root->left,val);
        TreeNode* p2=findsmall(root->right,val);
        if(p1!=NULL) result=p1;
        if(p2!=NULL)
        {
            if(result==NULL) result=p2;
            else 
                if(result->val>p2->val) result=p2;
        }
        return result;
    }
public:
    void recoverTree(TreeNode *root) 
    {
        if(root==NULL) return;
        TreeNode* left=findlarge(root->left,root->val);
        TreeNode* right=findsmall(root->right,root->val);
        if(left!=NULL && right!=NULL)
        {        
            swap(left->val,right->val);
            return;
        }
        if(right!=NULL)
        {
            swap(root->val,right->val);
            return;
        }
        if(left!=NULL)
        {
            swap(root->val,left->val);
            return;
        }
        recoverTree(root->left);
        recoverTree(root->right);
    }
};