当前位置：首页 > article >正文

【leetcode100】验证二叉搜索树

article 2025/1/22 10:17:48

1、题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

2、初始思路

2.1 思路

直接判断左右节点与中间节点的关系

# 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:
        if not root:
            return True
        if not root.left and not root.right:
            return True
        return root.left.val<root.val<root.right.val and self.isValidBST(root.left) and self.isValidBST(root.right)

2.2 犯错点

1、在直接访问左右节点时，没有考虑到其值为空的情况

2、没有考虑到二叉搜索树的全局性质，要求不仅满足单个子树条件，还要满足整体的条件。

3 优化算法

3.1 思路

定义左右节点的范围，从而更好地从全局对二叉搜索树进行检索。

# 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 search(node,l=-inf,r=inf):
            if not node:
                return True
            if node.val <= l or node.val >= r:
                return False
            return search(node.left, l, node.val) and search(node.right, node.val, r)
        return search(root)

查看全文

http://www.kler.cn/a/513349.html