题解 | #判断是不是二叉搜索树#

判断是不是二叉搜索树

http://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b

误区:单独判断某一个子树是否满足搜索树是不够的

class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        if not root:
            return True
        if root.left and root.left.val >= root.val:
            return False
        if root.right and root.right.val <= root.val:
            return False
        else:
            return self.isValidBST(root.right) and self.isValidBST(root.left)

解法:如果一个数是搜索树,则它的中序遍历一定是一个递增数列

class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # write code here
        # 中序遍历判断是否为单调增序列
        node_list = self.midOrder(root)
        for i in range(len(node_list) - 1):
            if node_list[i] >= node_list[i + 1]:
                return False
        return True
         
    def midOrder(self, node: TreeNode) -> list[int]:
        if not node:
            return []
        return self.midOrder(node.left) + [node.val] + self.midOrder(node.right)      
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 14:32
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务