来自“Pro Coder”示例的 Python 二进制搜索树

Question

所以我正在研究一个“简单的 Python 代码示例”，它检查一组节点是否形成二叉树，它应该评估并返回 True 或 False，完整代码如下：class Node(object):    def __init__(self, val, left = None, right = None):        self.val = val        self.right = right        self.left = leftclass Solution(object):    def _isValidBSTHelper(self, n , low, high):        if not n:            return True        val = n.val        if ((val > low and val < high) and           self._isValidBSTHelper(n.left, low ,n.val) and           self._isValidBSTHelper(n.right, n.val, high)):           return True        return False    def isValidBST(self, n):        return self._isValidBSTHelper(n, float('-inf'), float('inf'))##        (_5_)#       /        \#   (_4_)        (_7_)#  /     \      /     \#(_3_) (empty)(_6_)   (_8_)node = Node(5)node.right = Node(7)node.right.right = Node(8)node.left = Node(4)node.left.left = Node(3)node.right.left = Node(6)print(Solution().isValidBST(node))评论应该只是下面表达的节点的直观表示。我很难理解为什么float('-inf'), float('inf')需要def isValidBST(self, n):    return self._isValidBSTHelper(n, float('-inf'), float('inf'))以及 low, high, and n.val价值观如何发挥作用class Solution(object):    def _isValidBSTHelper(self, n , low, high):        if not n:            return True        val = n.val在理解此代码如何工作方面的任何帮助将不胜感激，谢谢

Answer 1

您应该做的第一件事是查看二叉搜索树的定义。您提出的所有问题都基于定义所施加的限制。

首先，考虑一个任意的 BST。你对它一无所知，除了它的结构。你被告知键是数字，所以你知道比较是数字比较。

那么，关于根节点，您能说些什么呢？没有什么。您知道它有一个数字键，但不知道该键是 1、0.0000000001 还是 10000000000。

但是有一个函数想要约束它，检查它是否小于某个值并大于某个值。如果只有某个数字大于所有其他数字……如果只有一个数字小于所有其他数字……

超越无限！

那就是从哪里来float('inf')的float('-inf')。编码员编写了一个函数，该函数采用“高”和“低”值。但是由于这棵树是任意的，我们所知道的还不足以提供有意义的值。因此，编码人员要么需要： 一个高于其他所有值的值；或检查代码以避免测试。

测试可以这样写：

if high is not None and val < high:

但这实际上减慢了速度，因为大概一旦我们进入树内部，就会（几乎）总是有一个高值和一个低值。因此，她改为使用float('inf')，因为这是“正无穷大”，一个大于所有其他值的值。（除了 Nan 和另一个正无穷大......）

同样对于低值 和float('-inf')，它是负无穷大并且低于所有数字。

最重要的是，这些数字是在树特定数据可用之前使用的作弊。

递归约束

现在考虑这些行：

       self._isValidBSTHelper(n.left, low ,n.val) and
       self._isValidBSTHelper(n.right, n.val, high)):

事实上，让我们摆脱垃圾并考虑一下：

       (n.left, low, n.val)
       (n.right, n.val, high)

第一个（上层）递归调用使用left当前节点的节点。也称为“左子树”。它说，“（左子树）中的所有内容都必须大于low我未触及的这个值，并且还必须小于当前节点值”。

这可以追溯到 BST 的定义：左子树中的所有内容都必须小于当前节点。

同样，第二个（较低的）递归调用不会更改值high，但表示“右子树中的所有内容都必须大于当前节点值”。再次，就在定义之外。

如果您查看评论中的图表，您会看到这些无穷大值沿着树的外侧传播。但是一旦代码移向树的中心，高值和低值都会从树节点中获取，它们将是有意义的具体测试。

例如，用 -Inf < 5 < +Inf 检查 5，用 5 < 7 < +Inf 检查 7，然后用 5 < 6 < +Inf 检查 6。

Answer 2

首先让我们澄清一下有效 BST 的属性是什么：

• 每个节点最多有两个孩子

• 该节点的值介于其左子节点（如果存在）和右子节点（如果存在）之间

  这意味着：左子值 < 节点值 < 右子值

• 此外，在普通情况下，任何空节点都是有效的 BST 。

现在您需要在每个节点检查这些属性，这就是该函数试图实现的目标：

• 首先它检查 node 的简单情况是 null - 返回 true

• 然后它检查节点的值是否在低值和高值之间，然后递归地检查它的左孩子和右孩子，因为属性需要在每个节点都有效！

现在，您最初会为根传递什么低值、高值？您会将所有节点中的最小值传递为低，将所有节点中的最大值传递为高，因为根节点的值位于它们之间。

如果您事先知道这些最小值、最大值，您可以将它们作为低值、高值传递。但是你不知道它们（好吧你可以发现如果你遍历 - 但它只是浪费时间），而不是你可以通过负边界和正边界的理论值。因为你确定节点的值肯定会在这两者之间。