Why most of the solutions use 'long' instead of others? Could someone explain it :)


  • -1
    J
    class Solution {
    

    public:
    bool isValidBST(TreeNode *root) {
    return check(root,LONG_MIN,LONG_MAX);
    }

    bool check(TreeNode *node,long min,long max){
        if(node==NULL) return true;
        if(node->val>=max||node->val<=min){
            return false;
        }
        bool left=check(node->left,min,node->val);
        if(left){
            return check(node->right,node->val,max);
        }
        return false;
    }
    

    };


  • 0
    D

    If only ints are used the function will falsely say a BST containing a node with a value of 2147483647 (MaxInt) or -2147483648 (MinInt) is invalid. This is because the function determines a node value that is equal to or greater than the upperBound or equal to or less than the lowerBound is not a valid BST. If we convert MaxInt and MinInt to longs and add 1 and subtract 1 from those values respectively we can get around the problem.

    public class Solution 
    {
        public bool IsValidBST(TreeNode root) 
        {
            return IsValidBST(root, (long)int.MinValue - 1, (long)int.MaxValue + 1);
        }
        
        private bool IsValidBST(TreeNode node, long lowerBound, long upperBound)
        {
            if (node == null) return true;
            if (node.val <= lowerBound || node.val >= upperBound) return false;
            return IsValidBST(node.left, lowerBound, node.val) && IsValidBST(node.right, node.val, upperBound);
        }
    }

Log in to reply
 

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