首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >这个检查BST(二进制搜索树)是否有效的函数可以在Python上运行吗

这个检查BST(二进制搜索树)是否有效的函数可以在Python上运行吗
EN

Stack Overflow用户
提问于 2018-08-01 08:29:28
回答 1查看 135关注 0票数 0

下面是我的代码,我的想法是,如果树中的最小值小于根,而树中的最大值大于根,则应该检查BST是否有效

    def min(self):
       while self.left:
           self.root = self.left
    return self.root

    def max(self):
        while self.right:
            self.root = self.right
    return self.value

    def valid(self):
        min = min(self.left)
        max = max(self.right)

        if self.root > min and self.root < max:
            return True
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-08-01 08:42:17

不要重复使用名称minmax。它们已经引用了内置函数。

您的minmax函数通过更改self.root来更改树。

您应该验证左子节点和右子节点相对于父节点的值是否正确,然后验证以这些子节点为根的每个BST本身是否有效。

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    def valid(self):
        if self.left and self.left.value > self.value:
            return False
        if self.right and self.right.value < self.value:
            return False
        return all(node.valid() for node in (self.left, self.right) if node)
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51623790

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档