Use long long int: c++ solution


  • 2
    P
    class Solution {
    public:
        bool Valid(TreeNode *rt,long long int low,long long int high){
            if(rt==NULL) return true;
            if(rt->val<=low || rt->val>=high) return false;
            return Valid(rt->left,low,rt->val)&&Valid(rt->right,rt->val,high);
        }
        bool isValidBST(TreeNode* root) {
            return Valid(root,(long long int)INT_MIN-1,(long long int)INT_MAX+1);
        }
    };

  • 0

    Another solution using Morris Traversal, an iterative one.


    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            if(!root) return true;
            int cur = 0; 
            long prev = (long)INT_MIN-1;
            bool flag = true; //using flag here to record the status to avoid return too early without restoring the tree which will cause Runtime Error.
            while(root)
            {
                if(!root->left)
                {
                    cur = root->val;
                    root = root->right;
                    if(cur <= prev) flag =  false;
                    prev = cur;
                }
                else
                {
                    TreeNode* pre = root->left;
                    while(pre->right && pre->right!=root)
                        pre = pre->right;
                    if(!pre->right)
                    {
                        pre->right = root;  
                        root = root->left;
                    }
                    else
                    {
                        pre->right = NULL;  //restore the tree;
                        cur = root->val;
                        root = root->right;
                        if(cur <= prev) flag = false;
                        prev = cur;
                    }
                }
            }
            return flag;
        }
    };

  • 0
    S

    I was getting an error in 67th test case until i used long long int can you please explain the use of it ?


  • 0
    P

    Because, in that case, the minimum node has value INT_MIN. Using this method, we want the lower bound be less than the minimum node. A proper choice is we pick low=INT_MIN-1. Using int, this number is overflowed, therefore, we need to use long long int. (sry for my poor English)


  • 0
    S

    Okay, that makes sense, but my code without the long long int didn't work for the 67th test case which had input as [2,1,4,7,4,8,3,6,4,7].
    I don't see any input being overflowed in this case.
    Here is the link to the code. https://leetcode.com/discuss/109877/easy-16ms-c-solution
    If you removed long long int from it, it wouldnt work for the above test. Can you please point ou the mistake.


  • 0
    P

    I remove the "long long int" and run the test. It fails at 67th test, but the input is
    "Input:
    [2147483647]"
    That is INT_MAX, one number.
    It is not [2,1,4,7,4,8,3,6,4,7] :)


Log in to reply
 

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