当前位置:网站首页>LC669. 修剪二叉搜索树
LC669. 修剪二叉搜索树
2022-07-01 21:45:00 【996冲冲冲】
迭代
def trimBST(self, root, low, high):
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
while root and (root.val < low or root.val > high): #找到合法的root
if root.val < low:
root = root.right
elif root.val > high:
root = root.left
cur = root
while cur:
while cur.left and cur.left.val < low: #找左边不合格的
cur.left = cur.left.right #找到之后左子树所有的都可以丢掉,并且把不合格节点的右子树连接到cur上
cur = cur.left #接着找(根据二叉树的特性没找到就一直往左找)
cur = root
while cur:
while cur.right and cur.right.val > high: #找右边不合格的
cur.right = cur.right.left #找到后右子树的所有都可以丢掉,并且把不合格节点的左子树连接到cur上
cur = cur.right #接着找(根据二叉树的特性没找到就一直往右找)
return root
递归
def trimBST(self, root, low, high): #从根节点开始修剪
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
if root.val < low:
return self.trimBST(root.right,low,high) #这里是进行修剪,并且最后返回修剪之后的结果(是先运行递归的语句,最后返回到当前语句时,才会执行return)
# 等价于
# left = self.trimBST(root.right,low,high) #先执行递归,返回到这一句时才会执行下面的那句
# return left
elif root.val > high:
return self.trimBST(root.left,low,high)
root.left = self.trimBST(root.left,low,high) #如果根节点没问题,则递归地修剪左子结点和右子结点
root.right = self.trimBST(root.right,low,high)
return root
递归,相当于自底向上的构建,先把所有的修剪完毕,之后return root时慢慢连接,最后把修剪好的左右子树连接上。
def trimBST(self, root, low, high):
""" :type root: TreeNode :type low: int :type high: int :rtype: TreeNode """
if not root:
return
if root.val >= low: #正常就修剪左子节点和右子节点
root.left = self.trimBST(root.left,low,high)
else: #如果根节点太小,且他的左子树都小于它所以直接返回右子树的修剪结果就行
return self.trimBST(root.right,low,high)
if root.val <= high:
root.right = self.trimBST(root.right,low,high)
else: #如果根节点太大,且他的右子树都大于它所以直接返回左子树的修剪结果就行
return self.trimBST(root.left,low,high)
return root
边栏推荐
- 名单揭晓 | 2021年度中国杰出知识产权服务团队
- 基于三维GIS的不动产管理应用
- MySQL之MHA高可用配置及故障切换
- 13th Blue Bridge Cup group B national tournament
- Clean up system cache and free memory under Linux
- 信标委云原生专题组组长,任重道远!
- QT 使用FFmpeg4将argb的Qimage转换成YUV422P
- MySQL series transaction log redo log learning notes
- [live broadcast review] the first 8 live broadcasts of battle code Pioneer have come to a perfect end. Please look forward to the next one!
- Design and practice of new generation cloud native database
猜你喜欢
I received a letter from CTO inviting me to interview machine learning engineer
Chapter 9 Yunji datacanvas company has been ranked top 3 in China's machine learning platform market
首席信息官对高绩效IT团队定义的探讨和分析
Recent public ancestor offline practice (tarjan)
[live broadcast review] the first 8 live broadcasts of battle code Pioneer have come to a perfect end. Please look forward to the next one!
并发编程系列之FutureTask源码学习笔记
Spark interview questions
100年仅6款产品获批,疫苗竞争背后的“佐剂”江湖
MySQL系列之事务日志Redo log学习笔记
Why does blocprovider feel similar to provider?
随机推荐
MySQL之MHA高可用配置及故障切换
Microsoft, Columbia University | Godel: large scale pre training of goal oriented dialogue
Interview question: what is the difference between MySQL's Union all and union, and how many join methods MySQL has (Alibaba interview question) [easy to understand]
CNN convolution neural network principle explanation + image recognition application (with source code) [easy to understand]
In the past 100 years, only 6 products have been approved, which is the "adjuvant" behind the vaccine competition
业务可视化-让你的流程图'Run'起来
locust 系列入门
Recent public ancestor (LCA) online practices
Communication between browser tab pages
Internet of things RFID, etc
使用闭包实现点击按钮切换 toggle
按照功能对Boost库进行分类
【MySQL】explain的基本使用以及各列的作用
Mysql——》Innodb存储引擎的索引
【MySQL】数据库优化方法
辅音和声母的区别?(声母与辅音的区别)
Airserver mobile phone third-party screen projection computer software
【直播回顾】战码先锋首期8节直播完美落幕,下期敬请期待!
What is the difference between PMP and NPDP?
微信小程序,连续播放多段视频。合成一个视频的样子,自定义视频进度条