来自 "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 = left


class 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'))

以及低值、高值和 n.val 值如何发挥作用

class Solution(object):
    def _isValidBSTHelper(self, n , low, high):
        if not n:
            return True
        val = n.val

如果您能帮助理解这段代码的工作原理，我们将不胜感激，谢谢

Answer 1

您应该做的第一件事是查看 Binary Search Tree 的定义。您提出的所有问题都基于定义所施加的限制。

首先，考虑任意 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 < 7 检查 6。