98. Validate Binary Search Tree

验证是否为bst

public boolean isValidBST(TreeNode root) {
    return dfs(root, null, null);
}

public boolean dfs(TreeNode root, TreeNode left, TreeNode right) {
    if (root == null) return true;
    if ((left != null && root.val <= left.val) || (right != null && root.val >= right.val)) return false;
    return dfs(root.left, left, root) && dfs(root.right, root, right);
}

每段都需要满足区间条件，否则return false

还有一种可以输入最大(最小)整数，但是这样可能会溢出，不如直接判断中间值是否为null

def isValidBST(self, root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    return self.dfs(root, -sys.maxsize, sys.maxsize)


def dfs(self, root, left, right):
    if not root:
        return True
    if root.val <= left or root.val >= right:
        return False
    return self.dfs(root.left, left, root.val) and self.dfs(root.right, root.val, right)