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

【代码随想录二刷】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.把二叉搜索树转换为累加树 语言&#xff1a;C 669. 修剪二叉搜索树 链接&#xff1a;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进行下载三、结论解决方法前言 在项目上线前夕&#xff0c;临时添加了个数据导出的接口&#xff0c;需求是导出压缩包&#xff0c;选择了项…...

python中savgol_filter的详细解释

目录savgol_filter简介savgol_filter原理参数window_length对平滑的效果参数polyorder的平滑效果savgol_filter简介 Savitzky-Golay滤波器最初由Savitzky和Golay于1964年提出&#xff0c;是光谱预处理中常用滤波方法&#xff0c;它的核心思想是对一定长度窗口内的数据点进行k阶…...

C语言--指针进阶1

目录回顾字符指针指针数组数组指针&数组名和数组名的区别数组指针的使用指针作为形参练习数组参数、指针参数一维数组传参二维数组传参一级指针传参二级指针传参回顾 指针的内容&#xff0c;我们在初级阶段已经有所涉及了&#xff0c;我们先来复习一下 指针就是个变量&am…...

ssh的使用

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

Apache Hadoop生态-目录汇总-持续更新

目录 1&#xff1a;系统服务分布图 3台分布式架构 1台单机架构 服务版本介绍 2&#xff1a;服务目录 存储相关 数据采集 任务调度 即席查询 数据可视化 集群监控 元数据管理 用户认证 权限管理 第三方windows客户端 1&#xff1a;系统服务分布图 3台分布式架构…...

「JVM 编译后话」编译器优化技术

后端编译&#xff08;即时编译、提前编译&#xff09;的目标时将字节码翻译成本地机器码&#xff0c;而难点是输出优化质量较高的机器码&#xff1b; 文章目录1. 优化技术概览2. 方法内联&#xff08;Inlining&#xff09;3. 逃逸分析&#xff08;Escape Analysis&#xff09;4…...

【python学习笔记】:输出与输入

01 输出方式 表达式语句、print()函数和使用文件对象的write()方法。 02 输出形式 格式化输出str.format()函数、转成字符串可以使用repr()或str()函数来实现。 (1)repr()&#xff1a;产生一个解释器易读的表达形式&#xff0c;便于字符串的拼接。 例&#xff1a;输出平方与…...

汽车电子社区交流宣传

http://t.csdn.cn/VSLO0http://t.csdn.cn/VSLO0 当今的汽车行业已经进入了数字化时代&#xff0c;汽车电子软件的开发变得越来越重要。在这个领域&#xff0c;开发者们需要应对各种挑战&#xff0c;包括复杂的硬件和软件交互、高效的嵌入式编程和安全性要求。为了帮助汽车电子…...

String、StringBuilder 和 StringBuffer 详解

碎碎念 这是一道老生常谈的问题了&#xff0c;字符串是不仅是 Java 中非常重要的一个对象&#xff0c;它在其他语言中也存在。比如 C、Visual Basic、C# 等。字符串使用 String 来表示&#xff0c;字符串一旦被创建出来就不会被修改&#xff0c;当你想修改StringBuffer 或者是 …...

windows服务器上传文件解决方案

1.说明 1.如果上传到linux系统&#xff0c;通常使用ftp相关技术&#xff0c;配合windows端的ftp客户端工具比如FileZilla等进行大文件的上传工作。 2.同理windows服务器也可以开启ftp服务用来传输大文件。 3.本文介绍偷懒方式&#xff08;常规是开启windows的ftp服务&#xff0…...

Android Studio翻译插件推介(Translation)

前言 Android Studio翻译插件适合英语水平不太好的程序员&#xff08;比如&#xff1a;我&#xff09;&#xff0c;最常用的翻译插件Translation和AndroidLocalize&#xff0c;本文主要讲解Translation&#xff0c;亲测可用。 先看看效果&#xff1a;这里是Android的API,任意选…...

DNS,DNS污染劫持,DNS加密

1. DNS&#xff08;Domain Name System&#xff09;DNS&#xff08;Domain Name System&#xff09;&#xff0c; 也叫网域名称系统&#xff0c;是互联网的一项服务。它实质上是一个 域名 和 IP 相互映射的分布式数据库.DNS&#xff08;Domain Name Server&#xff0c;域名服务…...

【Python】如何度量优秀代码——静态分析工具

静态分析工具背景有哪些静态分析工具呢度量Python代码的静态属性度量Python的生态系统代码的坏味道在类层面上在方法层面上结语背景 静态代码分析工具能够提炼出丰富的代码静态属性信息&#xff0c;这使得程序员可以对代码的复杂性、可修改性和可读性有进一步的了解。 有哪些…...

Open3D 点云高程归一化(基于2维地面点,Python版本)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 之前的博客中Open3D 点云高程归一化(基于地面点,Python版本)是基于三维空间进行最近地面点的查询操作,这里对其进行修改一下,将点云投影到水平面,基于二维空间进行最近地面点的查询,这种方式对一些较为陡峭的…...

动态系统的建模与分析

前言 CS小菜鸡控制理论入门 视频学习笔记 视频传送门&#xff1a;动态系统的建模与分析】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实现…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...