Exploiting that in-order traversal will have one or two wrong orders where replacements happen


  • -1
    P

    // Not sure why timing is bad. What could I have done better
    class Solution {
    public:
    TreeNode lastNode;
    void recoverTree(TreeNode
    root, TreeNode **leftNode, TreeNode **rightNode) {
    if (!root)
    {
    return;
    }

        recoverTree(root->left, leftNode, rightNode);
        if (lastNode != NULL)
        {
            
            if ((*leftNode) == NULL)
            {
                
                if (lastNode->val > root->val)
                {
                    (*leftNode) = lastNode;
                    (*rightNode) = root;
                }
            }
            else if (lastNode->val > root->val)
            {
                (*rightNode) = root;
                return;
            }
        }
        lastNode = root;
        recoverTree(root->right, leftNode, rightNode);
    }
    void recoverTree(TreeNode* root) {
        lastNode = NULL;
        TreeNode *leftNode = NULL, *rightNode=NULL;
        recoverTree(root, &leftNode, &rightNode);
        int temp= (leftNode)->val;
        (leftNode)->val = (rightNode)->val;
        (rightNode)->val = temp;
        
    }
    };

Log in to reply
 

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