【LeetCode+JavaGuide打卡】Day22|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

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

学习目标:

  • 235. 二叉搜索树的最近公共祖先
  • 701.二叉搜索树中的插入操作
  • 450.删除二叉搜索树中的节点

学习内容:

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

题目链接&&文章讲解
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。

//递归法
//从上向下去递归遍历,第一次遇到 cur节点是数值在[q, p]区间中,那么cur就是 q和p的最近公共祖先。
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) {TreeNode left = lowestCommonAncestor(root.left, p, q);if(left != null) return left;}//右if(root.val < p.val && root.val < q.val) {TreeNode right = lowestCommonAncestor(root.right, p, q);if(right != null) return right;}return root;}
}//迭代法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode cur = root;while(cur != null){if(cur.val > p.val && cur.val > q.val)  cur = cur.left;else if(cur.val < p.val && cur.val < q.val)  cur = cur.right;else return cur;}return null;}
}

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

题目链接&&文章讲解

//在叶子节点找到插入位置
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//终止条件if(root == null) {TreeNode node = new TreeNode(val);return node;}//左if(val < root.val){root.left = insertIntoBST(root.left, val);}//右if(val > root.val){root.right = insertIntoBST(root.right, val);}return root;}
}

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

题目链接&&文章讲解

有以下五种情况:

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了找到删除的节点
  • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
  • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
  • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
  • 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件//没有找到删除节点if(root == null) return null;//找到要删除的节点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(key < root.val){root.left = deleteNode(root.left, key);}if(key > root.val){root.right = deleteNode(root.right, key);}return root;}
}

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



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

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN