LeetCode 第98题--验证二叉搜索树
2024-09-06 17:01:38
1. 题目
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
2. 思路
这道题有多重解法,从根源来说,这是一个判断一棵树的中序遍历是不是一个升序。
2.1 使用递归
1.使用递归,使用递归的时候有一个坑,就是不能只判断当前值和左子树右子树的大小,而是要比较整棵树的极大值和极小值。
2.同时还要注意一点,每次递归的时候一定要选好终止位置,每一次我都选的恰好和正确答案错过。。。。。虽然说都能做出来,但是却有简单和复杂的区别。这道题的中止条件就是这个节点是不是空节点,我选的中止条件就是他是否还有子节点。
如果按照我的想法,就要分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,left =float('-inf'),right = float('inf') ) -> bool:
if not root:
return True
if (root.val <= left)or (root.val >= right):
return False
else:
return self.isValidBST(root.left,left,root.val) and self.isValidBST(root.right,root.val,right)
2.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:
list1 = []
def middlesearch(root1):
if not root1:
pass
else:
middlesearch(root1.left)
list1.append(root1.val)
middlesearch(root1.right)
middlesearch(root)
return list1 == sorted(list1) and len(set(list1)) == len(list1)
最新文章
- poj-2236-Wireless Network
- Android学习笔记之布局技巧以及布局中的细节介绍....
- Windows下IntelliJ IDEA中运行Spark Standalone
- Thrift——初学
- NHibernate从入门到精通系列
- [设计模式] 21 策略模式 Strategy
- 学习TextKit框架(上)
- rsync是类unix系统下的数据镜像备份工具
- 分层模型的典型应用和FishiGUI的分层模型
- WCF Test Client
- BZOJ 1664: [Usaco2006 Open]County Fair Events 参加节日庆祝( dp )
- (step4.2.1) hdu 1372(Knight Moves——BFS)
- Java字节码中的方法调用
- NYOJ--水池数目
- 第三篇:一个Spark推荐系统引擎的实现
- Sql语言简介——检索数据
- 面向对象之组合VS继承:继承过时了?
- MySQL5.7 并行复制配置
- Reduce 优化(mapr)
- 2019中山大学程序设计竞赛(重现赛) Clumsy Keke