【leetcode刷刷】235. 二叉搜索树的最近公共祖先 、701.二叉搜索树中的插入操作 、450.删除二叉搜索树中的节点

本文主要是介绍【leetcode刷刷】235. 二叉搜索树的最近公共祖先 、701.二叉搜索树中的插入操作 、450.删除二叉搜索树中的节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

235. 二叉搜索树的最近公共祖先

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 递归if not root: return if root.val == p.val: return pif root.val == q.val: return qleft = Noneright = Noneif root.val > p.val and root.val > q.val: left = self.lowestCommonAncestor(root.left, p, q)elif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)else:left = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right: return rootif left: return leftif right: return rightreturn       
  1. 自己写的时候,就是根据二叉树里的查找来写的逻辑,没有想到对于二叉搜索树而言,如果p/q在cur的两边,那么cur就是最近公共节点。想到这一点可以节约很多步骤。
  2. 下面给出了精简版
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 递归if not root: return if root.val == p.val: return pif root.val == q.val: return q  # 这个也包括在剩余的情况里?if root.val > p.val and root.val > q.val: left = self.lowestCommonAncestor(root.left, p, q)if left: return leftelif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)if right: return right# 剩下的就是在两边的,返回root就行。会不会存在两边都为None,那就找不到了,那也是rootreturn root
  1. 但事实上这题用迭代法非常简单,判断条件返回就可以了。但是关键是,知道之前讲的二叉搜索树和最近公共节点的简便判断条件。
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 迭代法cur = rootwhile(cur):if cur.val < p.val and cur.val < q.val: cur = cur.rightelif cur.val > p.val and cur.val > q.val:cur = cur.leftelse:return cur

701.二叉搜索树中的插入操作

  1. 一个简单的定义题?根据大小判断一下,保留前一个的指针,再插入就行
class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 二叉搜索树的插入if not root:return TreeNode(val)pre = Nonecur = rootwhile(cur):if val < cur.val:pre = curcur = cur.leftelse:pre = curcur = cur.rightprint(pre.val)if val < pre.val: pre.left = TreeNode(val)else:pre.right = TreeNode(val)return root
  1. 用递归法也可以。大概想法就是如果小于cur,就递归左边,大于就递归右边,None的时候返回新节点就行。这样就不用pre来记录前一个了。
class Solution:def insertIntoBST(self, root, val):if root is None:node = TreeNode(val)return nodeif root.val > val:root.left = self.insertIntoBST(root.left, val)if root.val < val:root.right = self.insertIntoBST(root.right, val)return root

450.删除二叉搜索树中的节点

  1. 脑袋已经递归晕了
class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if not root:return root# 应该把删除节点的右节点的最左子节点提上来if root.val == key:if not root.left and not root.right:return Noneelif not root.left: return root.rightelif not root.right: return root.leftelse:cur = root.rightwhile cur.left is not None:cur = cur.leftcur.left = root.leftreturn root.rightelif root.val < key:root.right = self.deleteNode(root.right, key)else: # print(root.val)root.left = self.deleteNode(root.left, key)return root

这篇关于【leetcode刷刷】235. 二叉搜索树的最近公共祖先 、701.二叉搜索树中的插入操作 、450.删除二叉搜索树中的节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/652234

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque