A constant space simple c++ solution


  • 0
    Y
    TreeNode *pre = nullptr;
    TreeNode *first = nullptr;
    TreeNode *second = nullptr;
    
    TreeNode *getEnd(TreeNode * x) { //get the end of subtree(x->left)
        TreeNode * y = x->left;
        while(y && y->right && y->right != x) y = y->right;
        return y;
    }
    
    void solve(TreeNode * cur) { //check pre and cur
        if(pre && pre->val > cur->val) {
            if(first == nullptr) first = pre;
            second = cur;
        }
        pre = cur;
    }
    public:
    void recoverTree(TreeNode* cur) {
        while(cur) {
            TreeNode *end = this->getEnd(cur);
            if(end == nullptr || end->right == cur) { //subtree(x->left) has done
                solve(cur);
                if(end) end->right = nullptr; //del the link
                cur = cur->right;
            } else { //go into subtree(x->left)
                end->right = cur; //add a link back to cur
                cur = cur->left;
            }
        }
        swap(first->val, second->val);
    }

Log in to reply
 

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