下面是我的代码,我的想法是,如果树中的最小值小于根,而树中的最大值大于根,则应该检查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
发布于 2018-08-01 08:42:17
不要重复使用名称min
和max
。它们已经引用了内置函数。
您的min
和max
函数通过更改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)
https://stackoverflow.com/questions/51623790
复制相似问题