当前位置:
首页 > temp > 简明python教程 >
-
LeetCode 98. 验证二叉搜索树 | Python
98. 验证二叉搜索树
题目来源:https://leetcode-cn.com/problems/validate-binary-search-tree
题目
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
解题思路
思路:中序遍历
根据题意,二叉搜索树有如下的性质:
- 当二叉树的左子树不是空时,左子树上的所有节点值都小于它根节点的值
- 当二叉树的右子树不为空时,右子树上所有节点值都大于根节点的值
- 左右子树同样也是二叉搜索树
从上面的性质可以看出,二叉搜索树【中序遍历】得到的值一定是升序的。那么就这个特性,我们在中序遍历的时候就可以考虑检查当前节点的值是否大于前一个中序遍历到的节点的值。如果都大于则说明这个序列是升序的,那么就与前面就性质所得出的结论是吻合的,那么整棵树就是二叉搜索树。
关于【中序遍历】,它是二叉树遍历的一种。在二叉树中,中序遍历首先遍历左子树,然后访问根节点,最后遍历右子树。
具体实现代码如下。
代码实现
# 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:
stack = []
# -inf 表负无穷
inorder = float('-inf')
while root or stack:
# 将左点压入栈中
while root:
stack.append(root)
root = root.left
# 进行中序遍历
root = stack.pop()
# 如果当前节点的值小于前面中序遍历的值时,就不是二叉搜索树
while root.val <= inorder:
return False
# 更新中序遍历的值
inorder = root.val
root = root.right
return True
实现结果
以上就是根据二叉搜索树的性质,用栈实现中序遍历的思路,进而解决《98. 验证二叉搜索树》问题的主要内容。
栏目列表
最新更新
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀(爬取学校通知公告)
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求:requests模块基础使用必知必会
Python初学者友好丨详解参数传递类型
如何有效管理爬虫流量?
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析:SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL,这些神奇的特性你知道吗?
openGauss内核分析:执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
SQL Server -- 解决存储过程传入参数作为s
关于JS定时器的整理
JS中使用Promise.all控制所有的异步请求都完
js中字符串的方法
import-local执行流程与node模块路径解析流程
检测数据类型的四种方法
js中数组的方法,32种方法
前端操作方法
数据类型
window.localStorage.setItem 和 localStorage.setIte
如何完美解决前端数字计算精度丢失与数