algorithm - 如果二叉树包含重复项或包含 +/- 无穷大，如何检查它是否是有效的 BST？

Question

我检查二叉树是否是 BST 的解决方案如下:

def is_BST(node):
  if node is None:
    return False

  stack = [(node, -float('inf'), float('inf')]
  while len(stack) > 0:
    node, lb, ub = stack.pop()
    if node.val <= lb or node.val >= ub:
      return False

    if node.left:
       stack.append((node.left, lb, node.val))
    if node.right:
       stack.append((node.right, node.val, ub))

  return True

但是如果树包含 -inf 或 inf，或者具有重复值，我的函数将无法正常工作。我怎样才能调整它以使其更普遍地工作？

Answer 1

你可以实现一个更优雅的递归函数，也可以使用set:

set = {-float('inf'), float('inf')}
isValid = True


def BST(node):

if(node is None):
    return

if node.value in set:
    global isValid
    isValid = False
else:
    set.add(node.value)

    BST(node.left)
    BST(node.right)

您的代码似乎运行不正常:

node, lb, ub = stack.pop()

这里您要删除节点，您必须保留所有数据以查找重复项。