Java solution after adding test cases


  • 8
    C

    Actually, not too much needs to be changed if you got AC code when extra test cases are not added. The only difference is add if-else condition for node's value equals INT_MAX and INT_MIN.

    public class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (root.left == null && root.right == null) {
                return true;
            }
            return check(root, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        
        public boolean check(TreeNode node, int max, int min) {
            if (node == null) {
                return true;
            }
            if (node.val > max || node.val < min) {
                return false;
            }
    
            // if node's value is INT_MIN, it should not have left child any more
            if (node.val == Integer.MIN_VALUE && node.left != null) {
                return false;
            }
            
            // if node's value is INT_MAX, it should not have right child any more
            if (node.val == Integer.MAX_VALUE && node.right != null) {
                return false;
            }
    
            return check(node.left, node.val - 1, min) && check(node.right, max, node.val + 1);
        }
    }

  • 0
    M

    Hi, can I change if(node.val > max || node.val < min) to if( node.val >= max || node.val <= min) and then change your return clause to check(node.left, node.val, min) && check(node.right, max, node.val)? However, the judgement system says that the input {-2147483648,#,2147483647} is wrong answer, but I tested it in Eclipse it's right, do you know why? Thanks!


  • 0
    C

    Check if your computer is 64bits, since the INTMAX and INTMIN leetcode used to test is based on 32bits (at least for this problem).


  • 5
    L

    Use Integer max and Integer min instead so that it can be initialized to null at the beginning. You don't need to worry about the condition for node's value equals INTMAX and INTMIN.

    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, null, null);
    }
    private boolean isValidBSTHelper(TreeNode root, Integer min, Integer max) {
        if(root == null)
            return true;
            
        if(min != null && root.val <= min)
            return false;
            
        if(max != null && root.val >= max) 
            return false;
            
        if(!isValidBSTHelper(root.left, min, root.val) || 
           !isValidBSTHelper(root.right, root.val, max))
            return false;
            
        return true;
    }

  • 0
    S

    RESOLVED, it was my mistake, oversight in code...

    Hi,

    I appreciate your code. Yet, I find a test being missed (i guess its not covered in evaluation):

    Tree:
    95
    94,96
    -,-,90,100

    Where '-' refers to null node and it is at each level. Your code returns True for this case, but actually the tree is invalid, isnt it?!


  • 0
    L

    Hi,

    Thanks for your feedback. I have tested my code and it will return false in this case.

        TreeNode root = new TreeNode(95);
        root.left = new TreeNode(94);
        root.right = new TreeNode(96);
        root.right.right = new TreeNode(100);
        root.right.left = new TreeNode(90);
        System.out.println(new Solution().isValidBST(root));

  • 0
    M

    Saving two lines of code by consolidating last three conditional statements.

    public class Solution {

    public boolean isValidBST(TreeNode root) {

        return helper(root,null, null);//MAXVALUE
    }
    
    public boolean helper(TreeNode root, Integer max, Integer min){ 
        if(root == null) return true;
        if(root.left != null)
        if(root.left.val >= root.val || (min != null && (root.left.val <= min) )|| !helper(root.left,root.val,min)) return false;
        
        if(root.right != null)
            if(root.right.val <= root.val || (max != null && (root.right.val >= max)) || !helper(root.right,max,root.val)) return false;
        return true;
    }
    

    }


Log in to reply
 

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