代码随想录算法训练营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

相关文章

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Redis过期删除机制与内存淘汰策略的解析指南

《Redis过期删除机制与内存淘汰策略的解析指南》在使用Redis构建缓存系统时,很多开发者只设置了EXPIRE但却忽略了背后Redis的过期删除机制与内存淘汰策略,下面小编就来和大家详细介绍一下... 目录1、简述2、Redis http://www.chinasem.cn的过期删除策略(Key Expir

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

Java Multimap实现类与操作的具体示例

《JavaMultimap实现类与操作的具体示例》Multimap出现在Google的Guava库中,它为Java提供了更加灵活的集合操作,:本文主要介绍JavaMultimap实现类与操作的... 目录一、Multimap 概述Multimap 主要特点:二、Multimap 实现类1. ListMult

深入解析 Java Future 类及代码示例

《深入解析JavaFuture类及代码示例》JavaFuture是java.util.concurrent包中用于表示异步计算结果的核心接口,下面给大家介绍JavaFuture类及实例代码,感兴... 目录一、Future 类概述二、核心工作机制代码示例执行流程2. 状态机模型3. 核心方法解析行为总结:三

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷