听：测试开发面试题解（12）- 验证二叉搜索树

测试开发面试题解 - 验证二叉搜索树

难度分类：中等

本文由何发奋撰写，旨在帮助读者理解如何判断一个二叉树是否为有效的二叉搜索树。二叉搜索树的特征包括：节点的左子树只有小于当前节点的数；节点的右子树只包含大于当前节点的数；所有左右子树都必须也是二叉搜索树。

文章通过例子展示了有效和无效的二叉搜索树，解释了在判断时需考虑左右子树与根节点的关系，并注意边界条件。如一个节点的右子树有小于其值的节点则不满足条件。

算法：在验证时，需要为每个子树设置左右边界，以确保左子树的值不大于左边界，右子树的值不小于右边界。代码示例使用递归函数helper，以无穷大和无穷小作为初始边界，逐步缩小范围进行判断。

    
def isValidBST(root):
    def helper(root,left_val=-float('inf'),right_val=float('inf')):
        if not root:
            return True
        val = root.val
        if val=right_val:
            return False
        if root.left and val=root.right.val:
            return False
        else:
            return helper(root.left,left_val,val) and helper(root.right,val,right_val)
    return helper(root)
    
  

文章最后鼓励读者，要想在测试开发领域取得成就，需要每日投入至少两小时学习时间，坚持写代码，才能在一年以上的时间内实现薪资的显著增长。

附有资源链接供读者免费领取试听课，以及相关测试开发的资料和课程推荐。

文章由 光荣之路出品，提供了招聘信息和社群链接，方便读者获得更多测试开发相关的机会和资源。