Don't forget to consider the case when Integer MINVALUE or MAX_VALUE exists in the tree

  • set min or max to null
  • or check whether it's MIN or MAX value
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, null, null);
    }

    private boolean isValidBSTHelper(TreeNode root, Integer low, Integer high) {
        if (root == null) return true;
        return (low == null || root.val > low) && (high == null || root.val < high) && isValidBSTHelper(root.left, low, root.val) && isValidBSTHelper(root.right, root.val, high);
    }
}
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        // write your code here
        return dfsHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean dfsHelper(TreeNode root, int min, int max) {

        if (root == null) return true;

        return (root.val > min || root.val == Integer.MIN_VALUE) && (root.val < max || root.val == Integer.MAX_VALUE) && dfsHelper(root.left, min, root.val) && dfsHelper(root.right, root.val, max);
    }
}

results matching ""

    No results matching ""