脚本宝典收集整理的这篇文章主要介绍了<LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Python,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
💖作者简介:大家好,我是车神哥,府学路18号的车神🥇 ⚡About—>车神:从寝室到实验室最快3分钟,最慢3分半(那半分钟其实是等红绿灯) 📝个人主页:应无所住而生其心的博客_府学路18号车神_CSDN博客 🎉点赞➕评论➕收藏 == 养成习惯(一键三连)😋 📖本系列主要以刷LeetCode(力扣)网站的各类题为标准,实现自我能力的提升为目标⚡ ⚡希望大家多多支持🤗~一起加油 😁
- 专栏—>《LeetCode天梯》
其他专栏:
- 《Neural Network》
- 《Python》
- 《Algorithm》
今天项目终于结题了,哇,熬了一晚上的夜,夜都被熬熟了,结题撒花,中午休息了下,下午继续卷起来呀,小伙伴们一起来。刷题不止,拒绝❌内卷,从我做起,哈哈哈,坚持吧!~
每天进步一点点,就已经很棒很棒了,坚持坚持,不要太累,拒绝内卷,从每日一练开始,每天十分钟,快乐生活一辈子!疫情依旧反复,大家带好口罩啊~ 继续继续,来,今天和车神哥一起来提升自己的Python编程和面试能力吧,刷天梯~
放上我拍的Photo吧!~ 今天喝了 luckin coffee
每日推荐一首歌:ゆうべは俺が悪かった
以下为我的天梯积分规则:
每日至少一题:一题积分+10分 若多做了一题(或多一种方法解答),则当日积分+20分(+10+10) 若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)
初始分为100分 若差一天没做题,则扣积分-10分(周六、周日除外注:休息) 坚持!!!
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
示例 1:
输入:root = [2,1,3] 输出:true
示例2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在[1, 10^4] 内
- -2^31 <= Node.val <= 2^31 - 1
分析:
可能由读者不知道中序遍历是什么,我们这里简单提及一下,中序遍历是二叉树的一种遍历方式,它先遍历左子树,再遍历根节点,最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值,根节点的值均小于右子树的值,因此中序遍历以后得到的序列一定是升序序列。(引用自了力扣原始解释,这个解释很通透!)
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%!!!
思路很不错!!!多多练习有大佬分析的很透彻,来看下面的图
注意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
增加上下界的写法:
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代码。
今天到这吧,加油❤作者:力扣 (LeetCode) 链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/ 来源:力扣(LeetCode)
作者:数据结构和算法 链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/?discussion=1Pu6Hw 来源:力扣(LeetCode)
今日得分:+10+10+20 总得分:690
加油!!!
❤坚持读Paper,坚持做笔记,坚持学习,坚持刷力扣LeetCode❤!!! 坚持刷题!!!打天梯!!! ⚡To Be No.1
⚡⚡哈哈哈哈
⚡创作不易⚡,过路能❤关注、收藏、点个赞❤三连就最好不过了
ღ( ´・ᴗ・` )
❤
『 纵使天光终将熄灭,我们也要歌颂太阳。 』
以上是脚本宝典为你收集整理的<LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Python全部内容,希望文章能够帮你解决<LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Python所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。