3 Java solutions (recursive, recursive in-order, iterative in-order)


  • 0
    E
    public class Solution1 {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        private boolean isValidBST(TreeNode root, long lowerBound, long upperBound){
            if (root == null) return true;
            if (root.val <= lowerBound || root.val >= upperBound) return false;
            return isValidBST(root.left, lowerBound, root.val) && isValidBST(root.right, root.val, upperBound);
        }
    }
    
    public class Solution2 {
        // recursive in-order
        // root.val should always larger than prev.val
        private TreeNode prev = null;
        public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            if (!isValidBST(root.left)) return false;
            if (prev != null && prev.val >= root.val) return false;
            prev = root;
            return isValidBST(root.right);
        }
    }
    
    
    public class Solution3 {
        // iterative in-order
        // root.val should always larger than prev.val
        public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode prev = null;
            while (root != null || !stack.isEmpty()){
                while (root != null){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (prev != null && prev.val >= root.val) return false;
                prev = root;
                root = root.right;
            }
            return true;
        }
    }
    

Log in to reply
 

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