Can anyone tell me why this code has Runtime error


  • 0
    G

    Hi all

    Here is my solution for Valid Binary Search Tree which is non-recursion version and inspired by Morris traversal that only use constant space. It works on my local machine, but it cannot pass the OJ, and it shows Runtime error. I cannot find the problem. Could anyone help find the bug. Thanks a lot.

    class Solution {
    public:
        bool isValidBST(TreeNode *root) {
            if (!root) return true;
            TreeNode *cur, *pre, *parent = NULL;
            cur = root;
            while (cur) {
                if (!cur->left) {
                    if (parent && parent->val >= cur->val) return false;
                    parent = cur;
                    cur = cur->right;
                } else {
                    pre = cur->left;
                    while (pre->right && pre->right != cur) pre = pre->right;
                    if (!pre->right) {
                        pre->right = cur;
                        cur = cur->left;
                    } else {
                        pre->right = NULL;
                        if (parent->val >= cur->val) return false;
                        parent = cur;
                        cur = cur->right;
                    }
                }
            }
            return true;
        }
    };

  • 0
    E

    Run time error is not necessarily coming from the test bench provided to you.
    Maybe you wanna try other cases on your local computer to see if there are any other errors like dead loop. Cause I got stuck at this one,lol.

    Here is my code of iteration, FYI. I am using stack to implement inorder traversal.

    class Solution2 {
    public:
        bool isValidBST(TreeNode *root) {
            stack<TreeNode *> myStack; 
            if(!root) return true;
            myStack.push(root);
            //use pointer rather than int_max to avoid int_max cases
            TreeNode *pre = nullptr; 
            while(!myStack.empty()){
                while(root && root->left){
                    myStack.push(root->left);
                    root = root->left;
    
                
            }
            root = myStack.top();
            myStack.pop();
            if(pre != nullptr && pre->val >= root->val) return false;
            pre = root; 
            root = root->right;
            if(root)
                myStack.push(root);
               
                
        }
        return true;
    }
    

    };


Log in to reply
 

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