99. Recover Binary Search Tree - cocoder39/coco39_LC GitHub Wiki

void recoverTree(TreeNode* root) {
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        
        while (cur) {
            if (! cur->left) {
                if (pre && cur->val < pre->val) { // a mistake
                    if (! first) {
                        first = pre;
                        second = cur; //bug
                    }
                    else {
                        second = cur;
                        //don't break before deleting thread
                    }
                }
                
                pre = cur;
                cur = cur->right;
            }
            else {
                TreeNode* predecessor = cur->left;
                while (predecessor->right != cur && predecessor->right) {
                    predecessor = predecessor->right;
                }
                if (! predecessor->right) {
                    predecessor->right = cur;
                    cur = cur->left;
                }
                else {
                    predecessor->right = nullptr;
                    if (pre && cur->val < pre->val) { // a mistake
                        if (! first) {
                            first = pre;
                            second = cur; // bug
                        }
                        else {
                            second = cur;
                            //don't break before deleting thread
                        }
                    }
                    pre = cur;
                    cur = cur->right;
                }
            }
        }
        
        swap(first->val, second->val);
    }