98. Validate Binary Search Tree

三刷 08/2022

Version #1 Recursion

Time O(N)

Space O(N)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.

Memory Usage: 41.7 MB, less than 94.90% of Java online submissions for Validate Binary Search Tree.

class Solution {

    public boolean isValidBST(TreeNode root) {

        return isValid(root, null, null);

    }

    //      5

    //    4   6

    //       3 7

    

    private boolean isValid(TreeNode node, Integer start, Integer end) {

        if (node == null) {

            return true;

        }

        if ((start != null && node.val <= start) || (end != null && node.val >= end)) {

            return false;

        }

        return isValid(node.left, start, node.val) && isValid(node.right, node.val, end);

    }

}

二刷 Version #3
stack
23.46 %
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev != null && curr.val <= prev.val) return false;
            prev = curr;
            curr = curr.right;
        }
        return true;
    }
}

Version #1 Using the definition of BST
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return isValidBST(root.left, Long.MIN_VALUE, root.val) &&
               isValidBST(root.right, root.val, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

Version #2 Using the property of BST
Do inorder traversal and check if the current value is larger than the previous value
二刷
38.60 %
public class Solution {
    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 Solution {
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (prev >= root.val) return false;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}