首页 > 试题广场 >

判断是不是二叉搜索树

[编程题]判断是不是二叉搜索树
  • 热度指数：81702 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

例：
图1

图2

数据范围：节点数量满足 ，节点上的值满足
示例1

输入

{1,2,3}

输出

false

说明

如题面图1
示例2

输入

{2,1,3}

输出

true

说明

如题面图2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python3
kuangk头像 kuangk 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    pre = -100000000000000
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        if not root:
            return True
        if not self.isValidBST(root.left):
            return False
        if root.val < self.pre:
            return False
        self.pre = root.val #给每一个节点（分支点）的值储存
        if not self.isValidBST(root.right):
            return False
        return True
        
        

编辑于 2024-03-05 11:03:43 回复(0)
Python3
可道非常道头像 可道非常道 
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        def helper(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True

            val = node.val
            if val <= lower&nbs***bsp;val >= upper:
                return False

            if not helper(node.left, lower, val):
                return False
            if not helper(node.right, val, upper):
                return False

            return True

        return helper(root)

发表于 2023-10-16 15:36:40 回复(0)
Python3
牛客429226965号头像 牛客429226965号
class Solution:
    pre = None
    result = True
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        def dfs(root):
            if root == None:
                return

            dfs(root.left)

            if self.pre == None:
                self.pre = root
                return

            if self.pre.val > root.val:
                self.result = False
                return

            self.pre = root
            dfs(root.right)

       
        dfs(root)
        return self.result
发表于 2023-08-10 11:30:18 回复(0)
Python3
Namely头像 Namely
中序遍历试试： 
class Solution:

    def inOrderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        return self.inOrderTraversal(root.left) + [root.val] + self.inOrderTraversal(root.right)

    def isValidBST(self , root: TreeNode) -> bool:
        res = self.inOrderTraversal(root)
        if len(res) <= 1:
            return True
        for i in range(len(res)-1):
            if res[i] >= res[i+1]:
                return False
        return True


发表于 2023-03-01 11:55:26 回复(0)
Python3
牛客781599455号头像 牛客781599455号
class Solution:
    def __init__(self):
        self.box=[]
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        if not root:
            return True
            if root.left==None and root.right==None:
                return True
        self.isValidBST(root.left)
        self.box.append(root.val)
        self.isValidBST(root.right)
        
        if self.box== sorted(self.box):
            return True
        else:
            return False
        
发表于 2022-10-31 23:55:22 回复(0)
提交观点

问题信息

树
难度：
5条回答 1966浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号