这个BST验证函数正确吗？

Question

我写了一些验证 BST 的逻辑，这似乎有效：

class Node:
  val: int
  left: 'Node | None' = None
  right: 'Node | None' = None

  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

# -----------------------

def isValidBST(root: Node, mn=float('-Inf'), mx=float('+Inf')) -> bool:
  if not (mn < root.val < mx):
    return False
  if root.left and not isValidBST(root.left, mn=mn, mx=root.val):
    return False
  if root.right and not isValidBST(root.right, mn=root.val, mx=mx):
    return False
  return True

我尝试根据此树定义对其进行测试：

#          5
#     2         9
#   0   4     7   10 
#           6

tree = Node(5,
            Node(2,
                 Node(0),
                 Node(4)),
            Node(9,
                 Node(7,
                      Node(6)),
                 Node(10)))

函数返回

True

。如果我使树无效（例如将 4 切换到 5 或 7 切换到 3），它会返回

False

。它似乎也在正确的时间停止，我检查了一些日志。

这个功能有效吗？不管怎样，它能以某种方式变得更好吗？

Answer 1

是的，它是正确且清晰的。您只能做一个非常小的改进，您可以使用 -inf 和 inf 代替 -Inf 和 +Inf，如下所示：

class Node:
  val: int
  left: 'Node | None' = None
  right: 'Node | None' = None

  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

# -----------------------

def isValidBST(root: Node, mn=float('-inf'), mx=float('inf')) -> bool:
  if not (mn < root.val < mx):
    return False
  if root.left and not isValidBST(root.left, mn=mn, mx=root.val):
    return False
  if root.right and not isValidBST(root.right, mn=root.val, mx=mx):
    return False
  return True