Any better solution?


  • 4
    X
    public boolean isValidBST(TreeNode root) {
    	return isValidNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidNode(TreeNode node, int min, int max) {
    	if (node == null)
    		return true;
    	if (node.val > max || node.val < min)
    		return false;
    	return isValidNode(node.left, min, node.val - 1) && isValidNode(node.right, node.val + 1, max);
    }

  • 0
    K

    Using in-order traverse, you can reduce the one variable "int max".

    bool isValidBST(TreeNode *root) {
        if (!root)
            return true;
        
        if (!isValidBST(root->left))
            return false;
            
        if (root->val <= prev)
            return false;
            
        prev = root->val;
        
        return isValidBST(root->right);
    }
    
    int prev = numeric_limits<int>::min();
    

  • 0
    G
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValid(TreeNode node, int min, int max) {
        return node == null || (min < node.val && node.val < max && isValid(node.left, min, node.val) && isValid(node.right, node.val, max));
    }

  • 0
    J

    Integer.MIN_VALUE - 1 and Integer.MAX_VALUE + 1 will cause overflows.


  • 0
    J

    @greatgrahambini Your solution failed for {Integer.MAX_VALUE, Integer.MIN_VALUE, #}


Log in to reply
 

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