算法打卡day19|二叉树篇08|Leetcode 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

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

算法题

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

题目链接:235. 二叉搜索树的最近公共祖先

大佬视频讲解:二叉搜索树的最近公共祖先视频讲解

个人思路

昨天做过一道二叉树的最近公共祖先,而这道是二叉搜索树,那就要好好利用这个有序的特点来解决这道题,因为是有序树,所以如果 中间节点是 q 和 p 的公共祖先,那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。

解法
递归法

那么只要从上到下去遍历,遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是p 和 q的公共祖先。但一定是最近公共祖先吗?画个图看看

如图下,从根节点搜索,第一次遇到 cur节点是数值在[q, p]区间中,即 节点7,此时可以说明 q 和 p 一定分别存在于 节点 7的左子树,和右子树中。

所以从上向下去递归遍历,第一次遇到 cur节点是数值在[q, p]区间中,那么cur就是 q和p的最近公共祖先.

这道题和二叉树的搜索还有一点不同,就是本题就是标准的搜索一条边的写法,遇到递归函数的返回值,如果不为空,立刻返回

再加上这道题没有递归顺序,因为这里没有中节点的处理逻辑;递归函数就很简单了如下

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root.val > p.val && root.val > q.val) //终止条件{return lowestCommonAncestor(root.left, p, q);}//递归过程if (root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);}return root;//返回参数}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)

迭代法

和递归法思路相似,改成了while循环,找到最近公共祖先就返回节点;

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {//遍历选择方向   if (root.val > p.val && root.val > q.val) {//若大了,就往小的方向靠即树的左边root = root.left;} else if (root.val < p.val && root.val < q.val) {root = root.right;} else {break;}}return root;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(1);(只有一个节点)


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

题目链接:701.二叉搜索树中的插入操作

大佬视频讲解:二叉搜索树中的插入操作视频讲解

个人思路

因为说还可以重构二叉树,一时间不知道怎么下手

解法
递归法

可以不考虑题目中提示所说的改变树的结构的插入方式,只考虑如何插入节点,只要按照二叉搜索树的规则去遍历,遇到空节点就插入节点就可以了。

递归三步走:

1.确定递归函数参数以及返回值

参数就是根节点指针,以及要插入元素,

递归函数需要有返回值,可以利用返回值完成新加入的节点与其父节点的赋值操作

递归函数的返回类型为节点类型TreeNode *

2.确定终止条件

终止条件就是找到遍历的节点为null的时候,就是要插入节点的位置了,并把插入的节点返回。

3.确定单层递归的逻辑

搜索树是有方向了,可以根据插入元素的数值,决定递归方向。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {// 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。if (root == null) { return new TreeNode(val);}if (root.val < val){root.right = insertIntoBST(root.right, val); // 递归创建右子树}else if (root.val > val){root.left = insertIntoBST(root.left, val); // 递归创建左子树}return root;}
}

时间复杂度:O(n);(最差遍历一遍树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)

迭代法

迭代的方法就需要记录当前遍历节点的父节点了,这个和没有返回值的递归函数实现的代码逻辑是一样的。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) return new TreeNode(val);TreeNode newRoot = root;TreeNode pre = root;//父节点while (root != null) {pre = root;if (root.val > val) {//利用二叉树特点root = root.left;} else if (root.val < val) {root = root.right;} }//当root为空时,就找到了插入节点的位置,再根据值的大小选择插入左边还是右边if (pre.val > val) {pre.left = new TreeNode(val);} else {pre.right = new TreeNode(val);}return newRoot;}
}

时间复杂度:O(n);(遍历整棵树)

空间复杂度:O(1);(因为是原地修改树的方式进行插入,不涉及递归调用栈的空间增长;除了返回的新节点外,算法不需要额外的空间来存储任何信息)


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

题目链接:450.删除二叉搜索树中的节点

大佬视频讲解:删除二叉搜索树中的节点视频讲解

个人思路

思路不清晰,主要是如何在删除节点后有多少种情况要解决不太明白

解法
递归法

因为二叉搜索树添加节点只需要在叶子上添加就可以的,不涉及到结构的调整,而删除节点操作涉及到结构的调整。这里使用递归函数的返回值来完成把节点从二叉树中移除的操作。

递归三步走:

1.确定递归函数参数以及返回值

上道题是通过递归返回值来加入新节点, 这里也可以通过递归返回值删除节点

2.确定终止条件

遇到空返回,其实这也说明没找到删除的节点,遍历到空节点直接返回了

3.确定单层递归的逻辑

二叉搜索树中删除节点遇到的情况有以下五种情况

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
    • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
    • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
    • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。

其中第五种情况比较难理解,画图理解,如下。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) return root;//终止条件if (root.val == key) {//找到删除节点if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;} else {TreeNode cur = root.right;while (cur.left != null) {cur = cur.left;}cur.left = root.left;//左右孩子都不为空的情况root = root.right;return root;}}if (root.val > key) root.left = deleteNode(root.left, key);//遍历左树if (root.val < key) root.right = deleteNode(root.right, key);return root;}
}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(n);(递归树的高度,如果是一个高度不平衡的树(例如链状结构)高度与n接近)

 迭代法

用迭代法模拟递归法中的逻辑来删除节点,但需要一个pre记录cur的父节点方便做删除操作

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null){return null;}//寻找对应的对应的前面的节点,以及他的前一个节点TreeNode cur = root;TreeNode pre = null;//父节点while (cur != null){if (cur.val < key){pre = cur;cur = cur.right;} else if (cur.val > key) {pre = cur;cur = cur.left;}else {break;}}if (pre == null){return deleteOneNode(cur);}if (pre.left !=null && pre.left.val == key){pre.left = deleteOneNode(cur);}if (pre.right !=null && pre.right.val == key){pre.right = deleteOneNode(cur);}return root;}public TreeNode deleteOneNode(TreeNode node){//处理删除节点的情况if (node == null){return null;}if (node.right == null){return node.left;}TreeNode cur = node.right;while (cur.left !=null){cur = cur.left;}cur.left = node.left;return node.right;}}

时间复杂度:O(n);(遍历二叉树)

空间复杂度:O(1);(因为是原地修改树的方式进行插入,不涉及递归调用栈的空间增长;除了返回的新节点外,算法不需要额外的空间来存储任何信息)


以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

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



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

相关文章

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

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

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

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

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

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

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

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