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

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

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

  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1Zt4y1F7ww/?share_source=copy_web&vd_source=af4853e80f89e28094a5fe1e220d9062
  • 题解(递归法):
/*** 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) {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;}
}
  • 题解(迭代法):
/*** 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) {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;}
}

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

  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html#%E6%80%9D%E8%B7%AF
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1Et4y1c78Y/?share_source=copy_web&vd_source=af4853e80f89e28094a5fe1e220d9062
  • 题解(递归法):
/*** 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) {//当前结点为空,说明找到了正好的插入位置//因为二叉搜索树插入均在叶子结点if(root == null){return new TreeNode(val);}if(root.val < val){//插入值大于当前结点,向右遍历//同时接收递归的右分支结点root.right = insertIntoBST(root.right, val);}if(root.val > val){//插入值小于当前结点,向左遍历//同时接收递归的左分支结点root.left = insertIntoBST(root.left, val);}//结束,返回新的二叉搜索树根结点return root;}
}
  • 题解(迭代法):
/*** 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) {//若传入二叉树为空,则直接返回nullif(root == null){return new TreeNode(val);}//双指针法初始化//root要参与双指针遍历,用newRoot记录二叉树根结点TreeNode newRoot = root;//pre与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指针遍历到了插入位置//此时root==null,pre为前一个结点的位置if(pre.val > val){//应插入到pre的左分支pre.left = new TreeNode(val);}else{//,比pre.val大,插入到右分支(题中元素不会有重复)pre.right = new TreeNode(val);}//返回添加结点后的二叉树return newRoot;}
}

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

  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/delete-node-in-a-bst/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1tP41177us/?share_source=copy_web&vd_source=af4853e80f89e28094a5fe1e220d9062
  • 难点图解:
(当待删除结点左右分支均不为空时的删除操作)

  • 题解(递归法):
/*** 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) {root = delete(root, key);return root;}public TreeNode delete(TreeNode root, int key){//若传入树为空,则直接返回nullif(root == null){return null;}if(root.val > key){// 若待删值在root左分支,进行左递归//并承接下一层递归的返回值root.left = delete(root.left, key);}else if(root.val < key){//若待删值在root右分支,进行右递归//并承接下一层递归的返回值root.right = delete(root.right, key);}else{//若找到待删结点//情况1、若待删结点左子树为空右子树不为空,//则直接返回当前结点右分支给root的上一层,删掉root,完成处理if(root.left == null && root.right != null){return root.right;}//情况2、若待删结点子右树为空左子树不为空,//则直接返回当前结点左分支给root的上一层,删掉root,完成处理if(root.left != null && root.right == null){return root.left;}//情况3、若待删结点左右子树均为空,则直接返回null给root上一层,完成删除if(root.left == null && root.right == null){return null;}//情况4、若待删结点左右子树均不为空,要保证删除后仍然满足搜索树,需要进一步处理//找到当前root右分支中的最左结点,这个结点就是最接近root的比root大的结点TreeNode temp = root.right;while(temp.left != null){temp = temp.left;}//当前,temp指向了root右分支的最左结点,而temp.left == null//把原root的左分支加到找到的temp结点的右分支上temp.left = root.left;//将原root的右分支的顶到root的位置上,完成删除操作root = root.right;}return root;}
}

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



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

相关文章

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