验证二叉搜索树

标签: 树 深度优先搜索 二叉搜索树 二叉树

难度: Medium

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

Submission

运行时间: 56 ms

内存: 18 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return False

        lastValue = float("-inf")

        def helper(root):
            nonlocal lastValue
            if root is None:
                return 
            if helper(root.left) is False:
                return False
            if lastValue >= root.val:
                return False
            else:
                lastValue = root.val
            if helper(root.right) is False:
                return False
        
        if helper(root) is False:
            return False
        return True

Explain

这个题解使用了中序遍历的思路来判断二叉树是否为有效的二叉搜索树。在二叉搜索树中，如果按照中序遍历的顺序遍历节点，得到的序列应该是严格单调递增的。题解定义了一个 lastValue 变量来记录上一个遍历到的节点的值，在递归遍历的过程中，比较当前节点的值和 lastValue，如果当前节点的值小于等于 lastValue，则说明不满足二叉搜索树的性质，返回 False。如果遍历完整个二叉树，没有返回 False，则说明该二叉树是有效的二叉搜索树。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return False

        lastValue = float("-inf") # 记录上一个遍历到的节点的值

        def helper(root):
            nonlocal lastValue
            if root is None:
                return 
            if helper(root.left) is False: # 递归遍历左子树
                return False
            if lastValue >= root.val: # 当前节点的值小于等于上一个节点的值，不满足二叉搜索树的性质
                return False
            else:
                lastValue = root.val # 更新 lastValue 为当前节点的值
            if helper(root.right) is False: # 递归遍历右子树
                return False
        
        if helper(root) is False:
            return False
        return True

Explore

在这个题解中，`helper(root)`递归函数用来遍历树并检查是否满足二叉搜索树的条件。这个函数只在发现不合法的情况（即当前节点的值不大于上一个节点的值）时返回`False`。当递归调用`helper(root.left)`或`helper(root.right)`时，如果返回`False`，则意味着已经发现了不满足条件的节点，因此无需继续遍历并直接返回`False`。如果递归调用没有返回`False`，则继续执行下一步的递归调用或操作。这种设计模式是为了提前终止遍历，并快速返回结果，避免不必要的计算。

根据二叉搜索树的定义，树中的每个节点的值都必须严格大于其左子树中的任何值，并严格小于其右子树中的任何值。因此，如果二叉树中存在具有相同值的节点，则不符合二叉搜索树的定义。在这个题解中，如果发现当前节点的值小于等于上一个遍历到的节点的值，将返回`False`，这包括了节点值相同的情况。因此，具有相同值的节点在此题解中被视为不满足二叉搜索树的条件。

在这个题解中，当`root`为`None`即树为空时返回`False`，这是因为没有节点来进行验证。然而，从定义上讲，一个空的二叉搜索树也是有效的。更好的处理方式是返回`True`当树为空时，因为空树符合二叉搜索树的所有条件。对于单节点的二叉树，它也应当被视为有效的二叉搜索树，因为它自然满足所有左子节点小于根节点，右子节点大于根节点的条件（尽管左右子节点都为空）。

题解中`lastValue`初始化为负无穷大是为了确保第一个节点的值总是大于`lastValue`。这种方法适用于任何数值类型，包括整数和浮点数，因为在Python中，`float('-inf')`是一个特殊的浮点数值，它比所有的浮点数和整数都小。因此，这种初始化方法是通用的，能够确保算法的正确初始条件。