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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>