【代码随想录二刷】Day23-二叉树-C++
代码随想录二刷Day23
今日任务
669.修剪二叉搜索树
108.将有序数组转换为二叉搜索树
538.把二叉搜索树转换为累加树
语言:C++
669. 修剪二叉搜索树
链接:https://leetcode.cn/problems/trim-a-binary-search-tree/
递归
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == NULL) return NULL;if(root->val < low) return trimBST(root->right, low, high);if(root->val > high) return trimBST(root->left, low, high);root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};
迭代
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == NULL) return NULL;while(root && (root->val < low || root->val > high)){if(root->val < low) root = root->right; //左边没必要修建了,都不符合条件else root = root->left;}//当前root的值肯定是位于[low,high]中的TreeNode* cur = root;while(cur){//左侧的值是更小的,直接剪掉while(cur->left && cur->left->val < low){cur->left = cur->left->right;}cur = cur->left;}cur = root;while(cur){//右侧的值是更大的,直接剪掉while(cur->right && cur->right->val > high){cur->right = cur->right->left;}cur = cur->right;}return root;}
};
108. 将有序数组转换为二叉搜索树
链接:https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
递归
class Solution {
public:TreeNode* traversal(vector<int>& nums, int left, int right){if(left > right) return NULL;if(left == right) return new TreeNode(nums[left]);int mid = left + ((right - left) >> 1);TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid - 1);root->right = traversal(nums, mid + 1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.size() == 1) return new TreeNode(nums[0]);return traversal(nums, 0, nums.size() - 1);}
};
迭代
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {queue<TreeNode*> nodeQue;queue<int> leftQue;queue<int> rightQue;TreeNode* root = new TreeNode(0);nodeQue.push(root);leftQue.push(0);rightQue.push(nums.size() - 1);while(!nodeQue.empty()){int left = leftQue.front(); leftQue.pop();int right = rightQue.front(); rightQue.pop();int mid = left + ((right - left) >> 1);TreeNode* cur = nodeQue.front(); nodeQue.pop();cur->val = nums[mid];if(left <= mid - 1){cur->left = new TreeNode(0);nodeQue.push(cur->left);leftQue.push(left);rightQue.push(mid - 1);}if(mid + 1 <= right){cur->right = new TreeNode(0);nodeQue.push(cur->right);leftQue.push(mid + 1);rightQue.push(right);}}return root;}
};
538. 把二叉搜索树转换为累加树
链接:https://leetcode.cn/problems/convert-bst-to-greater-tree/
递归
class Solution {
public:int sum = 0;int curSum = 0;void getSum(TreeNode* root){if(root == NULL) return;getSum(root->left);sum += root->val;getSum(root->right);}void traversal(TreeNode* root){if(root == NULL) return;traversal(root->left);int tmp = root->val;root->val = sum - curSum;curSum += tmp;traversal(root->right); }TreeNode* convertBST(TreeNode* root) {if(root == NULL) return root;getSum(root);traversal(root);return root;}
};
没有必要中序遍历,按照右中左遍历即可
class Solution {
public:int pre = 0;void traversal(TreeNode* root){if(root == NULL) return;traversal(root->right);root->val += pre;pre = root->val;traversal(root->left);}TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};
迭代
class Solution {
public:TreeNode* convertBST(TreeNode* root) {if(root == NULL) return root;int pre = 0;stack<TreeNode*> st;TreeNode* cur = root;//中序遍历反过来 while(!st.empty() || cur){if(cur){st.push(cur); //rootcur = cur->right;}else{cur = st.top();st.pop();cur->val += pre;pre = cur->val;cur = cur->left;}}return root;}
};
相关文章:
【代码随想录二刷】Day23-二叉树-C++
代码随想录二刷Day23 今日任务 669.修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 语言:C 669. 修剪二叉搜索树 链接:https://leetcode.cn/problems/trim-a-binary-search-tree/ 递归 class Solution { public:Tree…...
Linux GPIO 开发指南
文章目录Linux GPIO 开发指南1 概述1.1 编写目的1.2 适用范围1.3 相关人员2 模块介绍2.1 模块功能介绍2.2 相关术语介绍2.3 总体框架2.4 state/pinmux/pinconfig2.5 源码结构介绍3 模块配置3.1 kernel menuconfig 配置3.2 device tree 源码结构和路径3.2.1 device tree 对 gpio…...
记一次后端生成Zip文件通过浏览器下载后文件损坏,无法打开,不可预知的末端错误,下载后文件比源文件增大
记一次后端生成Zip文件问题前言问题出现排查一、流没有关好二、写入了空白字节三、没有flush定位环节一、生成二、通过SwaggerUI、PostMan进行下载三、结论解决方法前言 在项目上线前夕,临时添加了个数据导出的接口,需求是导出压缩包,选择了项…...
python中savgol_filter的详细解释
目录savgol_filter简介savgol_filter原理参数window_length对平滑的效果参数polyorder的平滑效果savgol_filter简介 Savitzky-Golay滤波器最初由Savitzky和Golay于1964年提出,是光谱预处理中常用滤波方法,它的核心思想是对一定长度窗口内的数据点进行k阶…...
C语言--指针进阶1
目录回顾字符指针指针数组数组指针&数组名和数组名的区别数组指针的使用指针作为形参练习数组参数、指针参数一维数组传参二维数组传参一级指针传参二级指针传参回顾 指针的内容,我们在初级阶段已经有所涉及了,我们先来复习一下 指针就是个变量&am…...
ssh的使用
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...
Apache Hadoop生态-目录汇总-持续更新
目录 1:系统服务分布图 3台分布式架构 1台单机架构 服务版本介绍 2:服务目录 存储相关 数据采集 任务调度 即席查询 数据可视化 集群监控 元数据管理 用户认证 权限管理 第三方windows客户端 1:系统服务分布图 3台分布式架构…...
「JVM 编译后话」编译器优化技术
后端编译(即时编译、提前编译)的目标时将字节码翻译成本地机器码,而难点是输出优化质量较高的机器码; 文章目录1. 优化技术概览2. 方法内联(Inlining)3. 逃逸分析(Escape Analysis)4…...
【python学习笔记】:输出与输入
01 输出方式 表达式语句、print()函数和使用文件对象的write()方法。 02 输出形式 格式化输出str.format()函数、转成字符串可以使用repr()或str()函数来实现。 (1)repr():产生一个解释器易读的表达形式,便于字符串的拼接。 例:输出平方与…...
汽车电子社区交流宣传
http://t.csdn.cn/VSLO0http://t.csdn.cn/VSLO0 当今的汽车行业已经进入了数字化时代,汽车电子软件的开发变得越来越重要。在这个领域,开发者们需要应对各种挑战,包括复杂的硬件和软件交互、高效的嵌入式编程和安全性要求。为了帮助汽车电子…...
String、StringBuilder 和 StringBuffer 详解
碎碎念 这是一道老生常谈的问题了,字符串是不仅是 Java 中非常重要的一个对象,它在其他语言中也存在。比如 C、Visual Basic、C# 等。字符串使用 String 来表示,字符串一旦被创建出来就不会被修改,当你想修改StringBuffer 或者是 …...
windows服务器上传文件解决方案
1.说明 1.如果上传到linux系统,通常使用ftp相关技术,配合windows端的ftp客户端工具比如FileZilla等进行大文件的上传工作。 2.同理windows服务器也可以开启ftp服务用来传输大文件。 3.本文介绍偷懒方式(常规是开启windows的ftp服务࿰…...
Android Studio翻译插件推介(Translation)
前言 Android Studio翻译插件适合英语水平不太好的程序员(比如:我),最常用的翻译插件Translation和AndroidLocalize,本文主要讲解Translation,亲测可用。 先看看效果:这里是Android的API,任意选…...
DNS,DNS污染劫持,DNS加密
1. DNS(Domain Name System)DNS(Domain Name System), 也叫网域名称系统,是互联网的一项服务。它实质上是一个 域名 和 IP 相互映射的分布式数据库.DNS(Domain Name Server,域名服务…...
【Python】如何度量优秀代码——静态分析工具
静态分析工具背景有哪些静态分析工具呢度量Python代码的静态属性度量Python的生态系统代码的坏味道在类层面上在方法层面上结语背景 静态代码分析工具能够提炼出丰富的代码静态属性信息,这使得程序员可以对代码的复杂性、可修改性和可读性有进一步的了解。 有哪些…...
Open3D 点云高程归一化(基于2维地面点,Python版本)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 之前的博客中Open3D 点云高程归一化(基于地面点,Python版本)是基于三维空间进行最近地面点的查询操作,这里对其进行修改一下,将点云投影到水平面,基于二维空间进行最近地面点的查询,这种方式对一些较为陡峭的…...
动态系统的建模与分析
前言 CS小菜鸡控制理论入门 视频学习笔记 视频传送门:动态系统的建模与分析】9_一阶系统的频率响应_低通滤波器_Matlab/Simulink分析 拉普拉斯变换 F(s)L{f(t)}∫0∞f(t)e−stdtF(s)\mathcal{L}\{f(t)\}\int_0^\infty f(t)e^{-st}\mathrm{d}tF(s)L{f(t)}∫0∞f(t)…...
QCC51XX---HCI log
高通在新的S3/S5以及往后新的平台上面,引入了一个新的调试功能。就是标题说的HCI log,他类似air trace那样用来分析蓝牙协议的,这样我们就可以很详细地找到通信协议之间哪个部分出了问题。以前我们都是通过抓包器抓air trace分析的,抓包器一个要几十万,学会这个功能就相当…...
Redis四 原理篇
《Redis四 原理篇》 提示: 本材料只做个人学习参考,不作为系统的学习流程,请注意识别!!! 《Redis四 原理篇》《Redis四 原理篇》1、原理篇-Redis数据结构1.1 Redis数据结构-动态字符串1.2 Redis数据结构-intset1.3 Redis数据结构-Dict1.4 Redis数据结构-ZipList1.4.1 Redis数据…...
从0开始写Vue项目-Vue实现数据渲染和数据的增删改查
从0开始写Vue项目-环境和项目搭建_慕言要努力的博客-CSDN博客从0开始写Vue项目-Vue2集成Element-ui和后台主体框架搭建_慕言要努力的博客-CSDN博客从0开始写Vue项目-Vue页面主体布局和登录、注册页面_慕言要努力的博客-CSDN博客从0开始写Vue项目-SpringBoot整合Mybatis-plus实现…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
