【代码随想录二刷】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实现…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
