算法-二叉搜索树的判断

wuchangjian2021-11-15 18:56:27编程学习

问题

给定一个二叉树,一个由二叉树节点组成的二叉树数据结构。每个二叉树节点都有一个整型值存储在名为“value”的属性中,两个子节点分别存储在名为“left”和“right”的属性中。子节点可以是二叉树节点本身,也可以是None(null)值。
**编写一个函数,返回一个表示二叉树是否为有效BST的布尔值。**当且仅当一个节点满足BST属性时,才称其为BST节点:

  • 其值严格大于其左侧每个节点的值;
  • 其值小于或等于其右侧每个节点的值;
  • 它的两个子节点要么是BST节点本身,要么是None(null)值;
    在这里插入图片描述

思路

思路比较简单的,就是判断每个节点是否满足二叉搜索树的性质:

  • 左子节点的value值要小于其根节点的value值
  • 右子节点的value值要大于其根节点的value值

思路一 : 如果是二叉搜索树,按照左根右中序遍历,则应该得到一个从小到大的排序列表,如果不满足,则不是二叉搜索树。
思路二: 遍历n个节点,判断当前节点是否满足二叉搜索树的性质,如果是左子节点,其最大值应该小于其父节点的值;如果是右子节点,其最小值应该大于其父节点的值。

实现

class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# O(n) time | O(d) space
def validateBst(tree):
    return validateBstHelper(tree, float("-inf"), float("inf"))


def validateBstHelper(tree, minValue, maxValue):
    if tree is None:
        return True
    if tree.value < minValue or tree.value >= maxValue:
        return False
    leftIsValid = validateBstHelper(tree.left, minValue, tree.value)
    rightIsValid = validateBstHelper(tree.right, tree.value, maxValue) 
    return leftIsValid and rightIsValid

相关文章

服务器常见命令2

创建并编写txt:  vim aa.txt    或者gedit aa.txt 查看...

311 复制文件的异常处理

311 复制文件的异常处理   【标准写法】 BufferedInputStre...

6运算符(很简单我就调难一点的来说)

算数运算符 运算符名称实例+加x + y-减x - y*乘x...

无法正常经营引发大量消费者投诉,每日优鲜被北京市消协约谈

2022-08-09 18:12:47 针对近日“每日优鲜”无法正常经...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。