LeetCode--098--验证搜索二叉树(python)
2024-08-27 14:42:22
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
示例 2:
低级做法,中序遍历,看看是否是有序的
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
def isValidBST(self, root: TreeNode) -> bool:
res_ = []
stack = []
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
res_.append(root.val)
root = root.right
stack=res_.copy()
stack.sort()
if len(set(stack)) != len(stack):
return False
return stack== res_
执行用时 :68 ms, 在所有 Python3 提交中击败了73.22%的用户
内存消耗 :16.8 MB, 在所有 Python3 提交中击败了7.23%的用户
每次将当前值和上下界进行比较,递归对其左右子树进行该过程:
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def helper(node, lower = float('-inf'), upper = float('inf')):
if not node:
return True val = node.val
if val <= lower or val >= upper:
return False if not helper(node.right, val, upper):
return False
if not helper(node.left, lower, val):
return False
return True return helper(root)
执行用时 :76 ms, 在所有 Python3 提交中击败了42.48%的用户
内存消耗 :16.2 MB, 在所有 Python3 提交中击败了39.06%的用
最新文章
- ASP.NET MVC5+EF6+EasyUI 后台管理系统(7)-MVC与EasyUI DataGrid
- Linux学习之一--VI编辑器的基本使用
- js文件上传
- php curl get
- 性能测试报告的指标选择、数据选择和分析的参考【以Apache AB test为例】
- Couldn&#39;t resolve Mac Server ";mymac";
- Android实战--短信发送器
- 我对序列化(Serializable)的理解
- shell脚本定时操作数据库
- matlab函数集锦
- java 注解Annotation
- C# 如何为应用程序加入多个图标?
- Rsync同步工具安装文档
- OpenGL蓝宝书第五章代码勘误以及惯性坐标系去解释模型变换:Pyramid.cpp
- 在VS中配置并测试opencv
- 关于php中的include html文件的问题,为什么html可以在php中执行
- SQL Android
- 如何检测或判断一个文件或字节流(无BOM)是什么编码类型
- Unity Remote 无法连接
- CentOS7安装redis数据库及php-redis扩展