当前位置: 首页 > news >正文

代码随想录算法训练营第二十天(二叉树 七)

day19 周日放假 今天依旧是二叉树环节

力扣题部分:

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

题目链接:. - 力扣(LeetCode)

题面:

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

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

思路:

        和day18的二叉树公共祖先不同的是,这一次我们可以利用二叉搜索树的特点遍历一个路径就够了,其他的倒没什么太大区别。

具体思路细节内容可以看day18的最后一题 236. 二叉树的最近公共祖先,这里就不重复了。

传送门(day18):代码随想录算法训练营第十八天(二叉树 六)-CSDN博客

代码实现:

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(p -> val > q -> val) swap(q, p);if(root -> val >= p -> val && root  -> val <= q -> val) return root;if(root -> val < p -> val && root -> right) return lowestCommonAncestor(root -> right, p, q);if(root -> val > q -> val && root -> left) return lowestCommonAncestor(root -> left, p, q);return nullptr;}
};

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

题目链接:. - 力扣(LeetCode)

题面:

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

思路:

        按照最简单的想法,一条路径走到底最后创造一个叶子节点挂树上就好了,可以不重构二叉树就不要重构二叉树了,不然就很麻烦(就像下一道题)。

代码实现:

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(!root){TreeNode* newnode = new TreeNode(val);return newnode;}if(root -> val > val) root -> left = insertIntoBST(root -> left, val);if(root -> val < val) root -> right = insertIntoBST(root -> right, val);return root;}
};

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

题目链接:. - 力扣(LeetCode)

题面:

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

思路:

        我们知道插入可以插入在叶子节点也可以不插入在叶子节点,而删除就没得选择,所有情况都要考虑,那就得按需要删除的结点情况分类讨论了:

1.没找到。

        解决办法:遍历到空节点直接返回。

2.找到了,在叶子节点上。

        解决办法:删除节点并返回空节点。

3.找到了,左边有子树右边没有。

        解决办法:像链表一样,要删除的节点的父节点指向要删除节点的左节点,相当于绕过要删除的节点,然后记得删除释放空间。

4.找到了,右边右子树左边没有。

        解决办法:第三条类似,父节点指向删除节点的右节点。

5.找到了,左右两边都有子树。

        解决办法:最难的部分。先讲操作:将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点

我们知道二叉搜索树要保证中序遍历递增,删除节点的左子树全部比右子树小,该节点一删右节点像之前一样一补上去,整个左子树就悬空了,由于左子树都比右子树小,所以只能把悬空的左子树根节点放在右节点最小的节点左侧,这样就可以让中序遍历仍旧是递增的了。(如果还有点懵,可以尝试画个图自己手动删除节点理解一下)

代码实现:

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一种情况if (root->val == key) {// 第二种情况if (root->left == nullptr && root->right == nullptr) {delete root;return nullptr;}// 第三种情况else if (root->left == nullptr) {auto retNode = root->right;delete root;return retNode;}// 第四种情况else if (root->right == nullptr) {auto retNode = root->left;delete root;return retNode;}// 第五种情况else {TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left;TreeNode* tmp = root;root = root->right;delete tmp;return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};

相关文章:

代码随想录算法训练营第二十天(二叉树 七)

day19 周日放假 今天依旧是二叉树环节 力扣题部分: 235. 二叉搜索树的最近公共祖先 题目链接:. - 力扣&#xff08;LeetCode&#xff09; 题面: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T …...

Django 后端架构开发:通用表单视图、组件对接、验证机制和组件开发

&#x1f31f; Django 后端架构开发&#xff1a;通用表单视图、组件对接、验证机制和组件开发 &#x1f539; django 通用表单视图 Django 的通用表单视图提供了快速创建和处理表单的功能&#xff0c;使得表单处理变得简洁而高效。以下示例展示了如何使用通用表单视图创建一个…...

Cookie和Session是什么?它们的区别是什么?

【知识】深入理解COOKIE&SESSION的原理和区别-腾讯云开发者社区-腾讯云 (tencent.com) Cookie和Session的区别&#xff08;面试必备&#xff09;_cookie和session的作用和区别-CSDN博客 Cookie和Session是什么&#xff1f;它们的区别是什么&#xff1f;_cookie里面的字符…...

Python正则表达式提取车牌号

在Python中使用正则表达式&#xff08;Regular Expressions&#xff09;来提取车牌号是一个常见的任务&#xff0c;尤其是在处理车辆信息或进行图像识别后的文本处理时。中国的车牌号格式多种多样&#xff0c;但通常包含省份简称、英文字母和数字。以下是一个使用Python正则表达…...

视觉引导机械臂学习记录

首先是几个位置&#xff0c;拍照位、示教位、目标位置。 流程主要是 1.首先选取一个拍照位&#xff0c;相机扫描点云&#xff0c;通过点云质量进行选取。并且制作点云模板&#xff0c;进行配准&#xff0c;如果配准分数高则模板选取正确。 2.用相机拍灰度图像&#xff0c;并…...

插屏广告在游戏APP中广告变现的独特优势

插屏广告是目前全球移动应用变现的主要广告形式之一&#xff0c;其优势在于可以快速收回成本&#xff0c;又能适应于多数缺乏激励场景的应用。 插屏广告通常在app使用过程中的自然过渡点&#xff0c;比如暂停场景切换的时候弹出&#xff0c;以图片、动图、视频等为表现形式的半…...

Python数据分析:数据可视化(Matplotlib、Seaborn)

数据可视化是数据分析中不可或缺的一部分&#xff0c;通过将数据以图形的方式展示出来&#xff0c;可以更直观地理解数据的分布和趋势。在Python中&#xff0c;Matplotlib和Seaborn是两个非常流行和强大的数据可视化库。本文将详细介绍这两个库的使用方法&#xff0c;并附上一个…...

Java CompletableFuture:你真的了解它吗?

文章目录 1 什么是 CompletableFuture&#xff1f;2 如何正确使用 CompletableFuture 对象&#xff1f;3 如何结合回调函数处理异步任务结果&#xff1f;4 如何组合并处理多个 CompletableFuture&#xff1f; 1 什么是 CompletableFuture&#xff1f; CompletableFuture 是 Ja…...

5个免费在线 AI 绘画网站推荐,附100+提示词!

在数字化时代&#xff0c;艺术创作与人工智能的结合已带来前所未有的创新体验。AI 绘画技术&#xff0c;基于先进的人工智能算法&#xff0c;为艺术创作提供了全新的视角和工具。当前&#xff0c;多个免费在线AI绘画平台应运而生&#xff0c;为创作者们提供了丰富的灵感和创作机…...

C++基础语法:while的使用

前言 "打牢基础,万事不愁" .C的基础语法的学习."学以致用,边学边用",编程是实践性很强的技术,在运用中理解,总结. 引入 while的使用是编写代码的基础内容.笔者的记忆力已不如以前,最近遇到了还花了不少功夫,可见是掌握地不够牢固.所以对while的思路和内容…...

鹏哥C语言自定义笔记重点(29-)

29.函数指针数组 30.void指针是不能直接解引用&#xff0c;也不能-整数。 void*是无具体类型的指针&#xff0c;可以接受任何类型的地址。 31.qsort:使用快速排序的思想实现一个排序函数(升序) 32. 33.地址的字节是4/8 34.char arr[]{a,b} sizeof(arr[0]1)答案是4&#xff0…...

代码随想录算法训练营第六十天 | dijkstra(堆优化版)、Bellman_ford 算法精讲

一、dijkstra&#xff08;堆优化版&#xff09; 题目连接&#xff1a;47. 参加科学大会&#xff08;第六期模拟笔试&#xff09; (kamacoder.com) 文章讲解&#xff1a;代码随想录 (programmercarl.com)——dijkstra&#xff08;堆优化版&#xff09; 二、Bellman_ford 算法精讲…...

boost::asio 库版本,C/C++代码编译兼容性

1、boost::asio::spawn 开启有栈&#xff08;stackful&#xff09;协同程序&#xff0c;版本改进及限制 > boost_1_80 版本应采用以下方式。 auto f [self, this](const boost::asio::yield_context& y) noexcept {bool success_ do_handshake(y);if (!success_) {clo…...

前端开发的项目导入方法与应用

前端项目启动问题归集&#xff1a; 由于前端的项目对于npm的版本有要求&#xff0c;需要将其升级到20&#xff0c;所以必要的时候通过nvm&#xff0c;或者直接下载最新的安装包进行npm覆盖安装。在项目目录中应用npm i安装node_modules&#xff0c;如果没有正常安装的话&#…...

C++:模拟实现string

前言&#xff1a; 为了更好的理解string底层的原理&#xff0c;我们将模拟实现string类中常用的函数接口。为了与std里的string进行区分&#xff0c;所以用命名空间来封装一个自己的strin类。 string.h #pragma once #define _CRT_SECURE_NO_WARNINGS 1#include<iostream&…...

浅谈Kafka(一)

浅谈Kafka&#xff08;一&#xff09; 文章目录 浅谈Kafka&#xff08;一&#xff09;Kafa的设计是什么样的数据传输的事务定义消息队列的应用场景Kafka怎么样判断节点是否存活Kafka的消息是采用pull模式还是push模式Kafka在磁盘上的消息格式Kafka高效文件存储设计特点Kafka与传…...

Redis7基础篇(八)

redis集群 是什么 能干吗 集群算法-分片-槽位slot redis集群的槽位slot redis集群的分片 分片和槽位的优势 槽位映射的解决方案 上面的三个方案分别对应了小厂 中厂 大厂 哈希槽取余分区 缺点 一致性哈希算法分区 小总结 哈希槽分区 经典面试题 这里说的redis是ap而不是cp的 …...

Tauri简介

在Tauri应用中&#xff0c;Rust和前端&#xff08;通常是基于Web技术如React、Vue或Angular&#xff09;之间的交互是一个核心特性&#xff0c;它允许开发者利用Rust的强大功能和性能&#xff0c;同时保持前端开发的灵活性和丰富的生态系统。这种交互主要通过Tauri提供的API桥接…...

JavaWeb——MVC架构模式

一、概述: MVC(Model View Controller)是软件工程中的一种 软件架构模式 &#xff0c;它把软件系统分为模型、视图和控制器三个基本部分。用一种业务逻辑、数据、界面显示分离的方法组织代码&#xff0c;将业务逻辑聚集到一个部件里面&#xff0c;在改进和个性化定制界面及用户…...

Excel求和方法之

一 SUM&#xff08;&#xff09;&#xff0c;选择要相加的数,回车即可 二 上面的方法还不够快。用下面这个 就成功了 三 还有一种一样快的 选中之后&#xff0c;按下Alt键和键&#xff08;即Alt&#xff09;...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...