Contact space, c++ solution, using morris traversal


  • 0
    I
    bool isValidBST(TreeNode* root) {
        TreeNode *cur = root, *prev = NULL, *last = NULL;
        bool isValid = true;
        while (cur != NULL) {
            if (cur->left == NULL) {
                if (last != NULL && last->val >= cur->val) isValid = false;
                last = cur;
                cur = cur->right;
            } else {
                prev = cur->left;
                while (prev->right != NULL && prev->right != cur) { prev = prev->right; }
                if (prev->right == NULL) {
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    if (last->val >= cur->val) isValid = false;
                    last = cur;
                    prev->right = NULL;
                    cur = cur->right;
                }
            }
        }
        return isValid;
    }

Log in to reply
 

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