为什么在Python中找到有效BST的测试用例很少失败？

Question

所以，我试图找到，给定二叉树的根，确定它是否是有效的二叉搜索树（BST）。

有效的 BST 定义如下：

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

所以，我的问题是很少有测试用例通过，但很少有测试用例没有通过，例如以下测试失败

以下是我的python代码，你能优化一下吗？

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):
        
        if not root:
            return []
        
        if self.isValidBST(root.left)< [root.val] < self.isValidBST(root.right):
            return True
        else:
            return False

所以，我已经编写了代码，但它的测试用例失败，输入如 root = [2,1,3]，输出为 false，但预期输出为 true。它通过了像 root = [5,1,4,null,null,3,6] 这样的测试用例

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。但重要的是要看到这个函数必须是与主函数不同的函数，因为主函数必须返回一个布尔值。

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