时间戳

首页 > 解决方案 > 使用递归验证二叉搜索树

python - 使用递归验证二叉搜索树

问题描述

我正在尝试验证二叉搜索树。给定二叉树的根，确定它是否是有效的二叉搜索树 (BST)。

有效的 BST 定义如下：

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

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

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

示例输入示例：[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"))

标签： pythondata-structurestree

解决方案

其实，你离得并不远。您只是错过了一个地方 - 请参阅代码：

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

[注] 受 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!

推荐阅读