来自“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'))

以及 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然后它检查节点的值是否在低值和高值之间，然后递归地检查它的左孩子和右孩子，因为属性需要在每个节点都有效！现在，您最初会为根传递什么低值、高值？您会将所有节点中的最小值传递为低，将所有节点中的最大值传递为高，因为根节点的值位于它们之间。如果您事先知道这些最小值、最大值，您可以将它们作为低值、高值传递。但是你不知道它们（好吧你可以发现如果你遍历 - 但它只是浪费时间），而不是你可以通过负边界和正边界的理论值。因为你确定节点的值肯定会在这两者之间。