I am trying to find a solution for LeetCode problem 98. Validate Binary Search Tree:

我正在努力寻找LeetCode问题98的解决方案。验证二叉搜索树：

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.


• The right subtree of a node contains only nodes with keys greater than the node's key.


• Both the left and right subtrees must also be binary search trees.

Following is the code that is already provided:

以下是已经提供的代码：

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

Following is my implementation:

以下是我的实现：

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

Problem

The code passes a few test cases (like root = [5,1,4,null,null,3,6]), but also fails a few. For example, it fails the following test:

代码通过了几个测试用例(如根=[5，1，4，NULL，NULL，3，6])，但也有几个失败。例如，它未通过以下测试：

• Input: root = [2,1,3], which represents this tree:

  输入：根=[2，1，3]，表示该树：

  
  

      2
     / \
    1   3
  

  
  



• Expected output: True

  预期输出：True

  
  

My code returns False.

我的代码返回FALSE。

What is my mistake?

我的错误是什么？

The main problem with this implementation is that isValidBST is supposed to return a boolean, so the following pieces of code don't make sense:

此实现的主要问题是，isValidBST应该返回一个布尔值，因此以下代码段没有意义：

• return []: that should be return True


• self.isValidBST(root.left)< [root.val]: this would be comparing a boolean with a list, which is not supported (nor does it have a meaning). Even if you expected the function to return a list here, that list would be empty (as you only return [] as a list -- see previous point).

A way to make it work is to pass extra (optional) arguments to isValidBST that provide a "window" (range) for the values of the given tree: all its nodes should have values within that window or it is not a BST. Initially that window can be set with default values to -Infinity to Infinity.

让它工作的一种方法是向isValidBST传递额外的(可选)参数，这些参数为给定树的值提供一个“窗口”(范围)：它的所有节点都应该在该窗口内有值，否则它不是BST。最初，该窗口可以用缺省值设置为-Infinity到Infinity。

Here is a spoiler in case you cannot make it work:

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

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

Alternatively you could make a helper function that does not return a boolean, but returns the window (range) that a given subtree actually spans (so its minimum and maximum values). If either span retrieved from the two subtrees violates the current root node's value, it is not a BST. But it is important to see that this function must be a different function from the main function, since the main function must return a boolean.

或者，您可以创建一个帮助器函数，该函数不返回布尔值，但返回给定子树实际跨越的窗口(范围)(因此它的最小值和最大值)。如果从两个子树中检索到的任何一个跨度与当前根节点的值冲突，则它不是BST。但重要的是，此函数必须是与主函数不同的函数，因为主函数必须返回布尔值。

Yet another alternative is to perform an inorder traversal. Each visited value must be greater than the previously visited value.

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