【算法训练记录——Day23】
Day23——二叉树Ⅸ
- 669.修剪二叉搜索树
- 108.将有序数组转换为二叉搜索树
- 538.把二叉搜索树转换为累加树
今日内容:
● 669.修剪二叉搜索树
● 108.将有序数组转换为二叉搜索树
● 538.把二叉搜索树转换为累加树
● 总结篇
669.修剪二叉搜索树

思路:主要是要理解如何删除,左子树小于val就要看左子树的右子树,这一步可以直接用左子树的右子树替换左子树。
遍历二叉树
1. low > root->val,返回root->right的处理结果
2. high < root->val 返回root->left的处理结果
3. 其他情况正常处理左右子树。
TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return root;if(root->val < low) {root = trimBST(root->right, low, high);} else if(root->val > high) {root = trimBST(root->left, low, high);} else {root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);}return root;}
迭代法暂时留着
108.将有序数组转换为二叉搜索树

思路:题本身不难,但是我又卡在了边界判断条件上,缝缝补补才出来,讨厌没有边界感的我!!!
其实还是没搞明白递归结束条件,等会看看题解。。。
TreeNode* recursion(vector<int>& nums, int left, int right) {if(left > right)return nullptr;int index = left + ((right - left) >> 1);if(index >= nums.size())return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index - 1);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size());}
思考一下,修改了点代码
上面方法的代码之所以越界,是因为当left == right == size的时候,但我的假设是左闭右开,所以sortedArrayToBST传入的是size,因此不能让left==size,并且 node->left = recursion(nums, left, index - 1)传入的right也没必要减1,减1是左闭右闭的思路
TreeNode* recursion(vector<int>& nums, int left, int right) {// 左闭右开if(left >= right)return nullptr;int index = left + ((right - left) >> 1);// if(index >= nums.size())// return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size());}
再来个左闭右闭,相等有意义,并且已访问值不再传入
TreeNode* recursion(vector<int>& nums, int left, int right) {// 左闭右闭if(left > right)return nullptr;int index = left + ((right - left) >> 1);// if(index >= nums.size())// return nullptr;TreeNode* node = new TreeNode(nums[index]);node->left = recursion(nums, left, index - 1);node->right = recursion(nums, index + 1, right);return node;} TreeNode* sortedArrayToBST(vector<int>& nums) {return recursion(nums, 0, nums.size() - 1);}
好好好,原来刚开始的代码是左闭右闭思路主函数没有减一引起的。
538.把二叉搜索树转换为累加树

思路:二叉搜索树中序遍历结果为递增(左根右),因此将中序遍历结果加入栈,然后遍历栈,修改元素值即可。
有没有一次遍历就修改的方法呢???想想。。除非倒着来,之前说过倒着来就是回溯,难道把中序遍历结果回溯???不会,看题解
好好好,把中序结果加入栈再出来,那不就是右根左吗。。。
TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return root;stack<TreeNode*> st;TreeNode* cur = root;int sum = 0;while(cur != nullptr || !st.empty()) {if(cur != nullptr) {st.push(cur);cur = cur->right;} else {cur = st.top();st.pop();sum += cur->val;cur->val = sum;cur = cur->left;}}return root;}
这几种遍历还是没玩明白呀
相关文章:
【算法训练记录——Day23】
Day23——二叉树Ⅸ 669.修剪二叉搜索树108.将有序数组转换为二叉搜索树538.把二叉搜索树转换为累加树 今日内容: ● 669.修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇 669.修剪二叉搜索树 思路:主要是…...
【wiki知识库】04.SpringBoot后端实现电子书的增删改查以及前端界面的展示
📝个人主页:哈__ 期待您的关注 目录 一、🔥今日内容 二、🌏前端页面的改造 2.1新增电子书管理页面 2.2新增路由规则 2.3修改the-header代码 三、🚗SpringBoot后端Ebook模块改造 3.1增加电子书增/改接口 3.1.…...
NTLM Relay Gat:自动化NTLM中继安全检测工具
关于NTLM Relay Gat NTLM Relay Gat是一款功能强大的NTLM中继威胁检测工具,该工具旨在利用Impacket工具套件中的ntlmrelayx.py脚本在目标环境中实现NTLM中继攻击风险检测,以帮助研究人员确定目标环境是否能够抵御NTLM中继攻击。 功能介绍 1、多线程支持…...
摸鱼大数据——Hive函数14
14、开窗(开列)函数 官网链接:Window Functions - Apache AsterixDB - Apache Software Foundation 14.1 基础使用 开窗函数格式: 开窗函数 over(partition by 分组字段名 [order by 排序字段名 asc|desc] [rows between 开窗开始 and 开窗结束]) partition b…...
elasticsearch的常规操作--增删改查和批量处理
1、_cat 查询 GET /_cat/nodes: 查看所有节点 GET /_cat/health: 查看es 健康状况 GET /_cat/master: 查看主节点 GET /_cat/indices:查看所有索引show databases; 2、索引一个文档(保存) 保存一个数据&…...
盘点2024年还在活跃发版的开源私有网盘项目附源码链接
时不时的会有客户上门咨询,丰盘ECM是不是开源项目,源码在哪里可以下载;如果需要和内部其他系统做集成,购买商业版的话,能否提供源代码做二次开发呢,等等诸多问题。 这里做个统一回复,丰盘ECM产…...
MySQL 使用方法以及教程
一、引言 MySQL是一个流行的开源关系型数据库管理系统(RDBMS),广泛应用于Web开发、数据分析等领域。它提供了高效、稳定的数据存储和查询功能。同时,Python作为一种强大的编程语言,也提供了多种与MySQL交互的库&#…...
算法学习笔记——二进制
二进制 负数的十进制转二进制数(-2 -> 1110): 正数 - 1,再取反,得到负数的二进制。 例如:-2 :0010 -> 0010 - 1 -> 0001 -> 取反 -> 1110 负数的二进制转十进制(…...
计算机网络介绍
计算机网络介绍 概述网络概述相关硬件 链路层VLAN概念VLAN 特点VLAN 的划分帧格式端口类型原理 STP概念特点原理 Smart Link概念特点组网 网络层ARP概念原理 IP概念版本IP 地址 IPv4IP 地址数据报格式 IPv6特点IP 地址数据报格式 ICMP概念分类报文格式 VRRP概念原理报文格式 OS…...
解锁数据宝藏:高效查找算法揭秘
代码下载链接:https://gitee.com/flying-wolf-loves-learning/data-structure.git 目录 一、查找的原理 1.1 查找概念 1.2 查找方法 1.3平均查找长度 1.4顺序表的查找 1.5 顺序表的查找算法及分析 1.6 折半查找算法及分析 1.7 分块查找算法及分析 1.8 总结…...
利用EasyCVR视频智能监控技术,构建智慧化考场监管体系
随着科技的进步,视频监控在各个领域的应用越来越广泛,其中在考场中的应用尤为显著。视频监控不仅能够提高考场的监管水平,确保考试的公平、公正和公开,还能有效预防和打击作弊行为,为考生营造一个良好的考试环境。 传…...
深度解析:速卖通618风控下自养号测评的技术要点
速卖通每年的618大促活动平台的风控都会做升级,那相对的测评技术也需要进行相应的做升级,速卖通618风控升级后,自养号测评需要注意以下技术问题,以确保测评 的稳定性和安全性: 一、物理环境 1. 硬件参数伪装&#x…...
国产算力——沐曦GPU性能及应用
沐曦集成电路(上海)有限公司(简称“沐曦”)成立于2020年9月,专注于为异构计算提供全栈GPU芯片及解决方案,满足数据中心对“高性能”、“高能效”及“高通用性”的算力需求。 产品系列 沐曦构建了全栈高性…...
贪心算法拓展(反悔贪心)
相信大家对贪心算法已经见怪不怪了,但是一旦我们的决策条件会随着我们的步骤变化,我们该怎么办呢?有没有什么方法可以反悔呢? 今天就来讲可以后悔的贪心算法,反悔贪心。 https://www.luogu.com.cn/problem/CF865Dhttp…...
在spring框架的基础上自定义autowired注解
在Spring框架的基础上自定义Autowired注解是不可能的,因为注解本身是Java语言的一部分,并且Autowired是Spring框架提供的注解,用于实现自动装配。但是,你可以创建自己的注解,并结合Spring框架的扩展机制来实现类似的功…...
2005NOIP普及组真题 3. 采药
线上OJ: [05NOIP普及组] 采药 核心思想: 1、题与 2006 年普及组第2题《开心的金明》一样,考察的都是01背包。 2、直接套用01背包的一阶模板即可 a、限定时间看成背包总容量m b、每件物品的采药时间 v 看成占用背包的体积 c、每件物品的价格w作为该物品的…...
preventDefault()与stopPropagation()有什么区别?
1、event.preventDefault()方法 (1)可防止元素的默认行为 (2)如果在表单元素中使用,它将阻止其提交 (3)如果在锚元素中使用,它将阻止其导航 (4)如果在上下…...
AIGC 全面介绍
随着人工智能技术的不断进步,生成式人工智能(AI Generated Content, AIGC)成为了一个日益热门的话题。AIGC 指利用人工智能技术生成各类内容,包括文本、图像、音频、视频等。与传统的内容生成方法相比,AIGC 具有速度快…...
网站入门:Flask用法讲解
Flask是一个使用Python编写的轻量级Web服务框架,旨在帮助开发人员快速构建和部署Web应用程序。下面将对Flask进行更为详细的解释说明,并展示其使用示例与注意事项: 1.解释说明 定义及特点: Flask以其简洁和灵活著称,允许开发者以…...
头歌数据库备份与恢复
第1关:数据库的备份和恢复 mysql -uroot -p123123 -h127.0.0.1 < /data/workspace/myshixun/src/data.sqlmysqldump -u root -p studb student> /student_bk.sqlmysql -uroot -p123123 -h127.0.0.1 -e "create database studb2;"mysql -u root -p123123 studb…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...
MLP实战二:MLP 实现图像数字多分类
任务 实战(二):MLP 实现图像多分类 基于 mnist 数据集,建立 mlp 模型,实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入,可视化图形数字; 2、完成数据预处理:图像数据维度转换与…...
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题
20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起,为了跨网段推流,千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...
