确定 BST 是否有效：某些测试用例失败

Question

我正在尝试寻找LeetCode问题98的解决方案。验证二叉搜索树:

给定二叉树的

root

，确定它是否是有效的二叉搜索树（BST）。

A 有效 BST 定义如下：

• 节点的左子树仅包含键小于节点键的节点。
• 节点的右子树仅包含键大于节点键的节点。
• 左右子树也必须都是二叉搜索树。

以下是已经提供的代码：

class TreeNode(object):
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

class Solution(object):
    def isValidBST(self, root):
        # your code

以下是我的实现：

class Solution(object):
    def isValidBST(self, root):
        if not root:
            return []
        if self.isValidBST(root.left)< [root.val] < self.isValidBST(root.right):
            return True
        else:
            return False

问题

代码通过了一些测试用例（如

root = [5,1,4,null,null,3,6]

），但也失败了一些。例如，它未通过以下测试：

• 输入：

  root = [2,1,3]

  ，代表这棵树：

      2
     / \
    1   3
  

• 预期输出：True

我的代码返回 False。

我的错误是什么？

Answer 1

此实现的主要问题是

isValidBST

应该返回布尔值，因此以下代码片段没有意义：

• return []

  ：应该是

  return True

• self.isValidBST(root.left)< [root.val]

  ：这会将布尔值与列表进行比较，这是不支持的（也没有意义）。即使您希望该函数在此处返回一个列表，该列表也将为空（因为您仅将

  []

  作为列表返回 - 请参阅上一点）。

使其工作的一种方法是将额外的（可选）参数传递给

isValidBST

，为给定树的值提供一个“窗口”（范围）：它的所有节点都应该在该窗口内具有值，否则它不是一个空白石板时间。最初可以将该窗口的默认值设置为 -Infinity 到 Infinity。

这里有一个剧透，以防你无法让它工作：

class Solution(object):
     def isValidBST(self, root, low=float('-inf'), high=float('inf')):
         return (not root or
                 low < root.val < high and self.isValidBST(root.left, low, root.val)
                                       and self.isValidBST(root.right, root.val, high))

或者，您可以创建一个辅助函数，它不返回布尔值，而是返回给定子树实际跨越的窗口（范围）（因此其最小值和最大值）。如果从两个子树检索到的任一跨度违反了当前根节点的值，则它不是 BST。但重要的是要看到这个函数必须是与主函数不同的函数，因为主函数必须返回一个布尔值。

另一种选择是执行中序遍历。每个访问过的值必须大于之前访问过的值。