代码随想录训练营Day22:● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

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

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

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

题目描述

相较于前一天的题不同,昨天的题是二叉树,这次重点强调了是二叉搜索树
在这里插入图片描述

思路

1、迭代法

因为二叉搜索树本身就是有序的,所以不需要去管前中后序三种遍历方法,直接判断大小即可整体思路就是判断 p,q 节点的值与根节点的大小,如果同时小于根节点,那公共祖先就在根节点的左子树 如果同时大于根节点,那么公共祖先就在根节点的右子树, 如果根节点的值介于两个节点之间,说明根节点就是祖先

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//迭代法if(root==null) return null;while (root!=null){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 {return root;}}return null;}
}

2、递归法

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;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;}
}

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

题目链接

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

题目描述

在这里插入图片描述

思路

public TreeNode insertIntoBST(TreeNode root, int val) {//递归方法//如果当前节点为空,说明此位置就是新节点将要插入的位置if(root==null) return new TreeNode(val);//如果根节点的值大于目标值,则向根节点的左侧递归//再判断如果根节点的左孩子不为空,继续递归,为空,就插入这里if(root.val>val){if(root.left!=null){insertIntoBST(root.left,val);}else {root.left = new TreeNode(val);}}//根节点大于目标值的思路类似上边if(root.val<val){if(root.right!=null){insertIntoBST(root.right,val);}else {root.right = new TreeNode(val);}}return root;
}

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

题目链接

https://leetcode.cn/problems/delete-node-in-a-bst/description/

题目描述

在这里插入图片描述

思路

第五种情况的处理逻辑:
在这里插入图片描述

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//本题可以分为五种情况//1、没有找到想要删除的元素//2、找到了想要删除的元素,且删除的元素是叶子节点,即左右孩子均为空//3、找到了想要删除的元素,且删除的元素左孩子不为空右孩子为空//4、找到了想要删除的元素,且删除的元素左孩子为空右孩子不为空//5、找到了想要删除的元素,且删除的元素左右孩子均不为空if(root==null) return root;if(root.val==key){if(root.left==null&&root.right==null){return null;}else if(root.left!=null&&root.right==null){return root.left;}else if(root.left==null&&root.right!=null){return root.right;}else {TreeNode cur = root.right;while (cur.left!=null){cur = cur.left;}cur.left=root.left;//此时将删除元素的左孩子放在了删除元素右孩子的最小的左孩子的位置//就相当于当前删除元素左孩子为空,右孩子不为空return root.right;}}if(root.val>key){//返回的节点应该用当前节点的左孩子接住root.left = deleteNode(root.left,key);}if(root.val<key){//返回的节点应该用当前节点的右孩子接住root.right = deleteNode(root.right,key);}return root;}
}

这篇关于代码随想录训练营Day22:● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》:本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete

SpringBoot操作MaxComputer方式(保姆级教程)

《SpringBoot操作MaxComputer方式(保姆级教程)》:本文主要介绍SpringBoot操作MaxComputer方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录引言uqNqjoe一、引入依赖二、配置文件 application.properties(信息用自己

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

HTML5 data-*自定义数据属性的示例代码

《HTML5data-*自定义数据属性的示例代码》HTML5的自定义数据属性(data-*)提供了一种标准化的方法在HTML元素上存储额外信息,可以通过JavaScript访问、修改和在CSS中使用... 目录引言基本概念使用自定义数据属性1. 在 html 中定义2. 通过 JavaScript 访问3.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

Python使用PIL库将PNG图片转换为ICO图标的示例代码

《Python使用PIL库将PNG图片转换为ICO图标的示例代码》在软件开发和网站设计中,ICO图标是一种常用的图像格式,特别适用于应用程序图标、网页收藏夹图标等场景,本文将介绍如何使用Python的... 目录引言准备工作代码解析实践操作结果展示结语引言在软件开发和网站设计中,ICO图标是一种常用的图像

C#中的 Dictionary常用操作

《C#中的Dictionary常用操作》C#中的DictionaryTKey,TValue是用于存储键值对集合的泛型类,允许通过键快速检索值,并且具有唯一键、动态大小和无序集合的特性,常用操作包括添... 目录基本概念Dictionary的基本结构Dictionary的主要特性Dictionary的常用操作

C# winform操作CSV格式文件

《C#winform操作CSV格式文件》这篇文章主要为大家详细介绍了C#在winform中的表格操作CSV格式文件的相关实例,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录实例一实例效果实现代码效果展示实例二实例效果完整代码实例一实例效果当在winform界面中点击读取按钮时 将csv中