[java/1ms] [min, max, isValid?] bottom up. Top down is also included.


  • 0

    You can't trust sub-tree's max and min unless it is a valid binary tree. Then you can use node.val > max(node.left) && node.val < min(node.right) to test.

    validate range from bottom to top

    public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            return validBST(root)[2] == 0;
        }
        
        private int[] validBST(TreeNode node) {
            if (node == null) return null;
            int val = node.val;
            int[] status = new int[3];
            // left node
            int[] left = validBST(node.left);
            if (left != null) {
                // not a valid tree, don't trust.
                if (left[2] == 1) return left; 
                if (val <= left[1]) {
                    status[2] = 1;
                    return status;
                } else {
                    status[0] = left[0];
                }
            } else {
                status[0] = val;
            }
            
            int[] right = validBST(node.right);
            if (right != null) {
                if (right[2] == 1) return right;
                if (val >= right[0]) {
                    status[2] = 1;
                    return status;
                } else {
                    status[1] = right[1];
                }
            } else {
                status[1] = val;
            }
            
            return status;
        }
    

    validate range from top to bottom

    public boolean isValidBST(TreeNode root) {
            return isValidBST(root, (long) Integer.MAX_VALUE + 1, (long) Integer.MIN_VALUE - 1);
        }
        
        private boolean isValidBST(TreeNode node, long ceiling, long floor) {
            if (node == null) return true;
            if (node.val >= ceiling || node.val <= floor) return false;
            return (
                    isValidBST(node.left, node.val, floor) 
                    && isValidBST(node.right, ceiling, node.val) 
            );
        }
    

Log in to reply
 

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