补-代码随想录第22天| ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

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

文章目录

  • ● 235. 二叉搜索树的最近公共祖先
    • 思路:
      • 一:递归
      • 二:迭代-利用特性
  • ● 701.二叉搜索树中的插入操作
    • 思路:
      • 思路一:递归
      • 代码:
      • 思路二:迭代
  • ● 450.删除二叉搜索树中的节点
    • 思路:递归
    • 代码:

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

在这里插入图片描述

思路:

一:递归

在这里插入图片描述
代码:

/*** 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.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;}
}

二:迭代-利用特性

代码:向左右分支去查找,找到则返回

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {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 {break;}}return root;}
}

● 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) {if(root==null)return new TreeNode(val);if(val<root.val)root.left=insertIntoBST(root.left,val);if(val>root.val)root.right=insertIntoBST(root.right,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) {if(root==null)return new TreeNode(val);TreeNode newRoot = root;TreeNode pre = root;while(root!=null){pre=root;//存父节点if(val<root.val){root=root.left;}else if(val>root.val){root=root.right;}}if (pre.val > val) {//添加新结点pre.left = new TreeNode(val);} else {pre.right = new TreeNode(val);}return newRoot;}
}

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

在这里插入图片描述

思路:递归

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
举例:
在这里插入图片描述

代码:

/*** 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) {// 第一种情况:没找到删除的节点,遍历到空节点直接返回了if(root==null)return root;if(root.val==key){// 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点if(root.left==null&&root.right==null){// root=null;return null;}// 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点else if(root.left==null&&root.right!=null){// root=root.right;return root.right;}// 第四种情况:其右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点else if(root.left!=null&&root.right==null){// root=root.left;return root.left;} // 第五种情况:左右孩子节点都不为空,// 则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else{TreeNode cur=root.right;while(cur.left!=null){// 把要删除的节点(root)左子树放在cur的左孩子的位置cur=cur.left;}cur.left=root.left;root=root.right;// 返回旧root的右孩子作为新rootreturn root;}}if (root.val > key)root.left=deleteNode(root.left,key);if (root.val < key)root.right=deleteNode(root.right,key);return root;}
}

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



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

相关文章

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中