合法二叉搜索树

难度: Medium

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

Submission

运行时间: 31 ms

内存: 17.9 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValid(self,root , min , max):
        if root == None:
            return True
        if root.val >= max or root.val <= min:
            return False
        else:
            return self.isValid(root.left,min,root.val) and self.isValid(root.right,root.val,max)


    def isValidBST(self, root: TreeNode) -> bool:
        return self.isValid(root,-1000000000000,1000000000000)

Explain

这个题解通过递归方式来判断二叉树是否为二叉搜索树（BST）。主要思路是使用辅助函数 isValid 来验证每个节点的值是否符合BST的定义。具体而言，每个节点的值必须大于其所有左子树节点的值并且小于其所有右子树节点的值。为了实现这一点，我们对每个节点设定一个值的范围，使用 min 和 max 两个参数记录当前节点值的有效范围。在递归过程中，对左子节点调用 isValid 时，更新最大值 max 为当前节点的值；对右子节点调用时，更新最小值 min 为当前节点的值。递归基是当遍历到空节点时，返回 true，因为空节点不违反BST的定义。如果节点的值不在当前的有效范围内，即大于等于 max 或小于等于 min，则返回 false。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValid(self, root, min, max):
        # Base case: an empty node is always valid
        if root == None:
            return True
        # Check if the current node's value is out of the valid range
        if root.val >= max or root.val <= min:
            return False
        # Recursively check the validity of the left and right subtree
        else:
            return self.isValid(root.left, min, root.val) and self.isValid(root.right, root.val, max)

    def isValidBST(self, root: TreeNode) -> bool:
        # Start the recursion with an arbitrary large range
        return self.isValid(root, -1000000000000, 1000000000000)

Explore

在定义isValid函数时，使用负无穷和正无穷作为初始的min和max值是为了确保根节点在初始检查时不受任何限制，从而可以接受任何整数值。这种方法在所有情况下都是适用的，因为它为根节点提供了可能的最广泛的值范围，避免了由于数据类型限制导致的问题。例如，如果使用整型的最大值和最小值作为边界，对于某些极端的树节点值（非常大或非常小的整数），这可能导致边界检查失败。使用负无穷和正无穷确保了算法的通用性和健壮性。

根据二叉搜索树（BST）的定义，对于任何节点，其左子树上的所有节点的值都必须严格小于该节点的值，而右子树上的所有节点的值都必须严格大于该节点的值。因此，如果在递归检查过程中，某个节点的值恰好等于其范围的min或max值，这意味着它违反了BST的这一性质。例如，如果一个节点的值等于其左子树的最大可能值（即该节点的值），则它不能同时是左子树的一个有效节点。因此，这种情况返回false是为了确保遵守BST的严格定义。

这种更新方法是基于BST的定义来设置的。在BST中，左子树的所有节点的值都必须小于其父节点的值，而右子树的所有节点的值都必须大于其父节点的值。因此，当递归检查左子树时，我们可以确定新的max值（即左子树中所有节点的值的上限）为当前节点的值，因为左子树中的任何节点都不应该大于这个值。同理，当检查右子树时，新的min值（即右子树中所有节点的值的下限）为当前节点的值。这种更新是按照BST的性质进行的，不会遗漏任何情况，而是确保所有子树节点都符合BST的规则。