<LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Python

简介: <LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Python

以下为我的天梯积分规则:


每日至少一题:一题积分+10分

若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)

若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)


初始分为100分

若差一天没做题,则扣积分-10分(周六、周日除外注:休息)

坚持!!!


初级算法

刷题目录

链表

image.png

题干

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

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

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

示例 1:

image.png

输入:root = [2,1,3]

输出:true

示例2:

image.png

输入:root = [5,1,4,null,null,3,6]

输出:false

解释:根节点的值是 5 ,但是右子节点的值是 4 。


提示:


树中节点数目范围在[1, 10^4] 内

-2^31 <= Node.val <= 2^31 - 1

中序遍历

分析:


可能由读者不知道中序遍历是什么,我们这里简单提及一下,中序遍历是二叉树的一种遍历方式,它先遍历左子树,再遍历根节点,最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值,根节点的值均小于右子树的值,因此中序遍历以后得到的序列一定是升序序列。(引用自了力扣原始解释,这个解释很通透!)

image.png

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
      if not root:
            return True
        prev = None 
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 若中序遍历得到的节点的值小于前一个值prev,那么就说明不是二叉搜索树,返回False
            if prev and root.val <= prev.val:
                return False
                # 保存上一节点
            prev = root
            root = root.right
        return True

这个速度超级快,超过100%!!!

image.png

思路很不错!!!多多练习

二叉树搜索(递归)

有大佬分析的很透彻,来看下面的图

image.png

注意6这个节点不光要小于15而且还要大于10,所以这里的每一个节点都是有一个范围的。这里我们来给每个节点添加一个范围,如果不在这个范围之内直接返回false,比如6的范围是(10,15),很明显他不在这个范围内,所以他不是二叉搜索树。下面方法可能不完全按照上面解释一致。

class Solution:
    prev = None  # 用于记录前一个节点
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        # 从左开始递归
        if not self.isValidBST(root.left):
            return False
        # 判断前一节点是否大于当前
        if self.prev is not None and self.prev.val >= root.val:
            return False
        # 保存前个节点
        self.prev = root
        # 右边递归
        if not self.isValidBST(root.right):
            return False
        return True

image.png

增加上下界的写法:

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
    # 递归并引入上界,下界来判断是否有效的二叉搜索树
    def chesh(node, min_val = float('-inf'), max_val = float('inf')) -> bool:
            if not node:
                return True
            #每个节点如果超过这个范围,直接返回false,设置出口
            if node.val <= min_val or node.val >= max_val:
                return False
            #这里再分别以左右两个子节点分别判断
            #左子树范围的最小值是minVal,最大值是当前节点的值,也就是root的值,因为左子树的值要比当前节点小   
            #右子数范围的最大值是maxVal,最小值是当前节点的值,也就是root的值,因为右子树的值要比当前节点大
            return chesh(node.left, min_val, node.val) and chesh(node.right, node.val, max_val)
        return chesh(root)

复现大佬的Java代码。

image.png


相关文章
|
3月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
|
4月前
|
Java 程序员 C++
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
50 0
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
|
6月前
|
算法 Python
python函数递归和生成器
python函数递归和生成器
|
6月前
|
数据采集 Java Python
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
|
5月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
|
6月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
146 2
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
99 1
|
5月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
6月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
92 7

热门文章

最新文章