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

【算法训练记录——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.把二叉搜索树转换为累加树 今日内容&#xff1a; ● 669.修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇 669.修剪二叉搜索树 思路&#xff1a;主要是…...

【wiki知识库】04.SpringBoot后端实现电子书的增删改查以及前端界面的展示

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 目录 一、&#x1f525;今日内容 二、&#x1f30f;前端页面的改造 2.1新增电子书管理页面 2.2新增路由规则 2.3修改the-header代码 三、&#x1f697;SpringBoot后端Ebook模块改造 3.1增加电子书增/改接口 3.1.…...

NTLM Relay Gat:自动化NTLM中继安全检测工具

关于NTLM Relay Gat NTLM Relay Gat是一款功能强大的NTLM中继威胁检测工具&#xff0c;该工具旨在利用Impacket工具套件中的ntlmrelayx.py脚本在目标环境中实现NTLM中继攻击风险检测&#xff0c;以帮助研究人员确定目标环境是否能够抵御NTLM中继攻击。 功能介绍 1、多线程支持…...

摸鱼大数据——Hive函数14

14、开窗(开列)函数 官网链接&#xff1a;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&#xff1a; 查看所有节点 GET /_cat/health&#xff1a; 查看es 健康状况 GET /_cat/master&#xff1a; 查看主节点 GET /_cat/indices&#xff1a;查看所有索引show databases; 2、索引一个文档&#xff08;保存&#xff09; 保存一个数据&…...

盘点2024年还在活跃发版的开源私有网盘项目附源码链接

时不时的会有客户上门咨询&#xff0c;丰盘ECM是不是开源项目&#xff0c;源码在哪里可以下载&#xff1b;如果需要和内部其他系统做集成&#xff0c;购买商业版的话&#xff0c;能否提供源代码做二次开发呢&#xff0c;等等诸多问题。 这里做个统一回复&#xff0c;丰盘ECM产…...

MySQL 使用方法以及教程

一、引言 MySQL是一个流行的开源关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;广泛应用于Web开发、数据分析等领域。它提供了高效、稳定的数据存储和查询功能。同时&#xff0c;Python作为一种强大的编程语言&#xff0c;也提供了多种与MySQL交互的库&#…...

算法学习笔记——二进制

二进制 负数的十进制转二进制数&#xff08;-2 -> 1110&#xff09;&#xff1a; 正数 - 1&#xff0c;再取反&#xff0c;得到负数的二进制。 例如&#xff1a;-2 &#xff1a;0010 -> 0010 - 1 -> 0001 -> 取反 -> 1110 负数的二进制转十进制&#xff08;…...

计算机网络介绍

计算机网络介绍 概述网络概述相关硬件 链路层VLAN概念VLAN 特点VLAN 的划分帧格式端口类型原理 STP概念特点原理 Smart Link概念特点组网 网络层ARP概念原理 IP概念版本IP 地址 IPv4IP 地址数据报格式 IPv6特点IP 地址数据报格式 ICMP概念分类报文格式 VRRP概念原理报文格式 OS…...

解锁数据宝藏:高效查找算法揭秘

代码下载链接&#xff1a;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视频智能监控技术,构建智慧化考场监管体系

随着科技的进步&#xff0c;视频监控在各个领域的应用越来越广泛&#xff0c;其中在考场中的应用尤为显著。视频监控不仅能够提高考场的监管水平&#xff0c;确保考试的公平、公正和公开&#xff0c;还能有效预防和打击作弊行为&#xff0c;为考生营造一个良好的考试环境。 传…...

深度解析:速卖通618风控下自养号测评的技术要点

速卖通每年的618大促活动平台的风控都会做升级&#xff0c;那相对的测评技术也需要进行相应的做升级&#xff0c;速卖通618风控升级后&#xff0c;自养号测评需要注意以下技术问题&#xff0c;以确保测评 的稳定性和安全性&#xff1a; 一、物理环境 1. 硬件参数伪装&#x…...

国产算力——沐曦GPU性能及应用

沐曦集成电路&#xff08;上海&#xff09;有限公司&#xff08;简称“沐曦”&#xff09;成立于2020年9月&#xff0c;专注于为异构计算提供全栈GPU芯片及解决方案&#xff0c;满足数据中心对“高性能”、“高能效”及“高通用性”的算力需求。 产品系列 沐曦构建了全栈高性…...

贪心算法拓展(反悔贪心)

相信大家对贪心算法已经见怪不怪了&#xff0c;但是一旦我们的决策条件会随着我们的步骤变化&#xff0c;我们该怎么办呢&#xff1f;有没有什么方法可以反悔呢&#xff1f; 今天就来讲可以后悔的贪心算法&#xff0c;反悔贪心。 https://www.luogu.com.cn/problem/CF865Dhttp…...

在spring框架的基础上自定义autowired注解

在Spring框架的基础上自定义Autowired注解是不可能的&#xff0c;因为注解本身是Java语言的一部分&#xff0c;并且Autowired是Spring框架提供的注解&#xff0c;用于实现自动装配。但是&#xff0c;你可以创建自己的注解&#xff0c;并结合Spring框架的扩展机制来实现类似的功…...

2005NOIP普及组真题 3. 采药

线上OJ&#xff1a; [05NOIP普及组] 采药 核心思想: 1、题与 2006 年普及组第2题《开心的金明》一样&#xff0c;考察的都是01背包。 2、直接套用01背包的一阶模板即可 a、限定时间看成背包总容量m b、每件物品的采药时间 v 看成占用背包的体积 c、每件物品的价格w作为该物品的…...

preventDefault()与stopPropagation()有什么区别?

1、event.preventDefault()方法 &#xff08;1&#xff09;可防止元素的默认行为 &#xff08;2&#xff09;如果在表单元素中使用&#xff0c;它将阻止其提交 &#xff08;3&#xff09;如果在锚元素中使用&#xff0c;它将阻止其导航 &#xff08;4&#xff09;如果在上下…...

AIGC 全面介绍

随着人工智能技术的不断进步&#xff0c;生成式人工智能&#xff08;AI Generated Content, AIGC&#xff09;成为了一个日益热门的话题。AIGC 指利用人工智能技术生成各类内容&#xff0c;包括文本、图像、音频、视频等。与传统的内容生成方法相比&#xff0c;AIGC 具有速度快…...

网站入门:Flask用法讲解

Flask是一个使用Python编写的轻量级Web服务框架&#xff0c;旨在帮助开发人员快速构建和部署Web应用程序。下面将对Flask进行更为详细的解释说明&#xff0c;并展示其使用示例与注意事项&#xff1a; 1.解释说明 定义及特点: Flask以其简洁和灵活著称&#xff0c;允许开发者以…...

头歌数据库备份与恢复

第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…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...