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

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

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

这道题较为简单,只需要通过递归找到符合要求的叶子节点,并将节点插入即可。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//遇到节点为空,就返回一个val值的节点,相当于将该节点接到子节点的左子树或者右子树上if(root == null) return new TreeNode(val);//如果val小于root.val,说明应该往左边插入if(val < root.val) root.left = insertIntoBST(root.left,val);//如果val大于root.val,说明应该往右边插入else root.right = insertIntoBST(root.right,val);//返回完成操作之后的root即可return root;}
}

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

这道题就复杂得多,删除节点所涉及的情况有五种,因为遇到要删除的节点需要立马删除,所以将删除的操作体现在终止条件里,并返回删除之后的root节点。
删除的节点的五种可能性:
1.整个二叉数都没有key节点
2.key节点在叶子节点上
3.key节点的右节点不为空,左节点为空,返回root.left
4.key节点的左节点为空,右节点不为空,返回root.right
5.key节点的左右节点都为不为空,这种情况是最复杂的,需要先将key节点左子树接到右子树最小值的左边
如下图所示,我们要删除的key为11,那么再删除之前,要将左子树处理一下。
在这里插入图片描述
将左子树拼接到右子树上那个比自己根节点大一点点的那个节点的左边,然后删除val=11的节点
在这里插入图片描述
最后得到了这个处理之后的二叉树
在这里插入图片描述
代码如下:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件较为复杂,有五种不同的情况。并且key节点发现即要删除,因此删除的操作也包含在终止条件中//情况一:没有找到key,返回nullif(root == null) return null;//后四种情况属于找到key节点的这一前提下的子情况if(root.val == key){//情况二:找到的key为叶子结点,直接删除即可//因为后面会用父节点的左子树去承接,因此返回null相当于删除if(root.left == null && root.right == null) return null;//情况三:左空右不为空else if(root.left == null && root.right != null) return root.right;//情况四:右空左不为空else if(root.left != null && root.right == null) return root.left;//情况五:左右均不为空//需要先将左子树移到右子树中最小的节点的左子树上,以保证删除后符合平衡TreeNode cur = root.right;while(cur.left != null) cur = cur.left;cur.left = root.left;//将当前节点删除return root.right;}//需要判断向哪一边去寻找要删除的key节点if(key > root.val) root.right = deleteNode(root.right,key);if(key < root.val) root.left = deleteNode(root.left,key);return root;}
}

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

236. 二叉树的最近公共祖先

这两个题目可以用一套相同的解法,代码如下:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {//因为从下往上去处理,因此可以用左右中的后序遍历public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return returnNode(root,p,q);}public TreeNode returnNode(TreeNode root, TreeNode p, TreeNode q){//终止条件,遇到空或者q或者q就可以返回了if(root == null) return null;//遇到空即返回if(root.val == p.val || root.val == q.val) return root;//如果遇到p或者q,就返回root//左TreeNode leftNode = returnNode(root.left,p,q);//右TreeNode rightNode = returnNode(root.right,p,q);//中if(leftNode != null && rightNode != null) return root;else if(leftNode == null && rightNode != null) return rightNode;else if(leftNode != null && rightNode == null) return leftNode;else return null;}
}

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



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

相关文章

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

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

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

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

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于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的常用操作