Simple 33 line C++ solution


  • 0
    K

    Basically there are two cases:

    1. adjacent elements are swapped
    2. distant elements are swapped

    if adjacent elements are swapped then we will find only one inversion between previous and root but if distant elements are swapped then we will find two instances of inversion between root and previous

    Accordingly we set ptr1 and ptr2.

    TreeNode *ptr1,*ptr2;
        void inorder(TreeNode *root,TreeNode* &previous)
        {
            if(root==NULL)
                return;
            inorder(root->left,previous);
            if(previous!=NULL&&previous->val>=root->val)
            {
                if(ptr1==NULL)
                {
                    ptr1=previous;
                    ptr2=root;
                }
                else
                    ptr2=root;
            }
            previous=root;
            inorder(root->right,previous);
            return;
        }
        void recoverTree(TreeNode* root)
        {
            int p1,p2,temp;
            ptr1=NULL;
            ptr2=NULL;
            if(root==NULL)
                return;
            TreeNode *previous=NULL;
            inorder(root,previous);
            temp=ptr1->val;
            ptr1->val=ptr2->val;
            ptr2->val=temp;
            return;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.