使用递归验证二叉搜索树

Question

我试图验证二叉查找树。给定二叉树的根，确定它是否是有效的二叉查找树（BST）。

有效的BST定义如下：

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

https://leetcode.com/problems/validate-binary-search-tree/

我正在使用递归解决方案，但它未能通过以下测试用例：
输入：[2,1,3]
预期输出：True
我的输出：False

示例输入：[5,1,4， null， null，3,6]
预期输出：False
我的输出：False

有人能指出我的错误吗？下面是我的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        
        def valid(node, left, right):
            if not node:
                return True
            
            if not (node.val>left and node.val<right):
                return False
            
            return (valid(node.left, left, node.val) and valid(node.right, node.val, right))
                    
        return valid(root, float("-inf"), float("-inf"))

Answer 1

可以通过在递归中为左侧和右侧节点提供一系列值来下推验证。这样，每个节点只需根据其父节点传递的需求检查自己，然后为自己的子节点递归。

def isBST(node,minVal=None,maxVal=None):
    if node is None: return True
    if minVal is not None and self.val<minVal: return False 
    if maxVal is not None and self.val>maxVal: return False
    if not isBST(self.left,minVal,self.val):   return False
    if not isBST(self.right,self.val,maxVal):  return False
    return True

Answer 2

事实上，你离得不远。你只是错过了一个地方——看代码：

这里的想法是相同的，但代码略有不同，以匹配您的原始代码。逻辑并与你的帖子进行比较。

[注]灵感来源于Alain和OP递归思想。所以要归功于他们。；-）

 def isValidBST(self, root: TreeNode) -> bool:
     
     def validate(node, lower, upper):
         if not node:  return True    # empty node/Tree considered BST

         # compare the node range is still valid: between low and high
         if node.val > lower and node.val < upper:
            return validate(node.left, lower, node.val) and \
                   validate(node.right, node.val, upper)
            return False
     return validate(root, float("-inf"), float("+inf")) # <--- miss here!