【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

相关文章

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND

Python使用openpyxl读取Excel的操作详解

《Python使用openpyxl读取Excel的操作详解》本文介绍了使用Python的openpyxl库进行Excel文件的创建、读写、数据操作、工作簿与工作表管理,包括创建工作簿、加载工作簿、操作... 目录1 概述1.1 图示1.2 安装第三方库2 工作簿 workbook2.1 创建:Workboo

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

Ubuntu 24.04启用root图形登录的操作流程

《Ubuntu24.04启用root图形登录的操作流程》Ubuntu默认禁用root账户的图形与SSH登录,这是为了安全,但在某些场景你可能需要直接用root登录GNOME桌面,本文以Ubuntu2... 目录一、前言二、准备工作三、设置 root 密码四、启用图形界面 root 登录1. 修改 GDM 配

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象(Map/List)转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach