代码随想录第18天：二叉树
一、修剪二叉树（Leetcode 669）
递归法
class Solution:def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:# 如果当前节点为空，直接返回空节点（递归终止条件）if root is None:return None# 如果当前节点的值小于低值 low，说明当前节点及其左子树都不符合条件# 所以应该修剪左子树，直接递归修剪右子树if root.val < low:return self.trimBST(root.right, low, high)# 如果当前节点的值大于高值 high，说明当前节点及其右子树都不符合条件# 所以应该修剪右子树，直接递归修剪左子树if root.val > high:return self.trimBST(root.left, low, high)# 当前节点的值在 [low, high] 范围内，保留该节点# 递归修剪左子树和右子树，并将修剪后的左右子树重新连接到当前节点root.left = self.trimBST(root.left, low, high) # 修剪左子树root.right = self.trimBST(root.right, low, high) # 修剪右子树# 返回修剪后的树return root
迭代法：
class Solution:def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:# 如果当前节点为空，直接返回 None（递归的终止条件）if not root:return None# 处理头结点，确保 root 在区间 [L, R] 内# 如果 root.val 小于 L，说明左子树所有的节点也小于 L，所以应该向右移动# 如果 root.val 大于 R，说明右子树所有的节点也大于 R，所以应该向左移动while root and (root.val < L or root.val > R):if root.val < L:root = root.right # 如果当前节点小于 L，跳到右子树else:root = root.left # 如果当前节点大于 R，跳到左子树cur = root # 此时 root 应该已经在 [L, R] 范围内# 处理左子树：确保所有左子树的节点值大于等于 Lwhile cur:# 如果当前节点的左子树的节点值小于 L，应该删除这些节点while cur.left and cur.left.val < L:cur.left = cur.left.right # 将左子树的左子节点修剪掉，跳到下一个右子节点cur = cur.left # 移动到左子树，继续修剪cur = root # 重置 cur 为 root，继续处理右子树# 处理右子树：确保所有右子树的节点值小于等于 Rwhile cur:# 如果当前节点的右子树的节点值大于 R，应该删除这些节点while cur.right and cur.right.val > R:cur.right = cur.right.left # 将右子树的右子节点修剪掉，跳到下一个左子节点cur = cur.right # 移动到右子树，继续修剪# 返回修剪后的根节点return root
二、将有序数组转换为二叉搜索树（Leetcode 108）
高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。本题关键就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
递归法：
class Solution:def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:# 递归终止条件：如果左索引大于右索引，说明已经没有元素可以加入树中，返回 Noneif left > right:return None# 计算中间元素的索引，用它来构建树的根节点mid = left + (right - left) // 2# 创建树的根节点，它是数组中的中间元素root = TreeNode(nums[mid])# 递归构建左子树root.left = self.traversal(nums, left, mid - 1)# 递归构建右子树root.right = self.traversal(nums, mid + 1, right)# 返回当前构建好的节点（树的根节点）return rootdef sortedArrayToBST(self, nums: List[int]) -> TreeNode:# 调用递归函数来构建树，初始的左右索引是从 0 到 len(nums) - 1root = self.traversal(nums, 0, len(nums) - 1)# 返回构建好的二叉搜索树return root
迭代法：
from collections import dequeclass Solution:def sortedArrayToBST(self, nums: List[int]) -> TreeNode:if len(nums) == 0:return None # 如果输入的数组为空，直接返回 Noneroot = TreeNode(0) # 初始根节点，值为 0，后面会替换nodeQue = deque() # 用于存储正在遍历的节点leftQue = deque() # 用于存储当前节点左子树的区间rightQue = deque() # 用于存储当前节点右子树的区间nodeQue.append(root) # 将根节点入队列leftQue.append(0) # 左区间初始位置为 0rightQue.append(len(nums) - 1) # 右区间初始位置为 len(nums) - 1while nodeQue:curNode = nodeQue.popleft() # 从队列中取出当前节点left = leftQue.popleft() # 当前节点的左区间right = rightQue.popleft() # 当前节点的右区间mid = left + (right - left) // 2 # 计算中间位置curNode.val = nums[mid] # 将中间位置的元素赋值给当前节点# 处理左子树if left <= mid - 1:curNode.left = TreeNode(0) # 创建左子树节点nodeQue.append(curNode.left) # 将左子树节点入队leftQue.append(left) # 左子树的区间rightQue.append(mid - 1) # 左子树的右区间为 mid - 1# 处理右子树if right >= mid + 1:curNode.right = TreeNode(0) # 创建右子树节点nodeQue.append(curNode.right) # 将右子树节点入队leftQue.append(mid + 1) # 右子树的左区间为 mid + 1rightQue.append(right) # 右子树的右区间return root # 返回最终的树根节点
三、把二叉搜索树转换为累加树（Leetcode 538）
本题类似数组从后向前累加，从树中可以看出累加的顺序是右中左，所以我们需要“反中序遍历”（右中左）这个二叉树，然后顺序累加
递归法：
class Solution:def convertBST(self, root: TreeNode) -> TreeNode:self.pre = 0 # 记录前一个节点的值，初始为0self.traversal(root) # 从根节点开始递归遍历return root # 返回修改后的根节点def traversal(self, cur):if cur is None:return # 如果当前节点为空，直接返回self.traversal(cur.right) # 先递归右子树，因为我们需要从大到小访问节点cur.val += self.pre # 将当前节点的值加上已遍历的节点值self.pre = cur.val # 更新当前的前一个节点值self.traversal(cur.left) # 再递归左子树
迭代法：
class Solution:def __init__(self):self.pre = 0 # 用于记录前一个节点的累加值，初始为0def traversal(self, root):stack = [] # 用来模拟递归过程的栈cur = root # 当前节点初始化为根节点# 栈不为空或者当前节点不为空时，继续遍历while cur or stack:if cur: # 如果当前节点不为空stack.append(cur) # 将当前节点压入栈cur = cur.right # 先处理右子树，因为我们需要逆序遍历else:cur = stack.pop() # 弹出栈顶元素（中序遍历的当前节点）# 当前节点的值加上之前累加的值cur.val += self.preself.pre = cur.val # 更新前一个节点的累加值cur = cur.left # 转到左子树继续遍历def convertBST(self, root):self.pre = 0 # 重置累加值self.traversal(root) # 开始遍历并转换树return root # 返回转换后的根节点
相关文章：
代码随想录第18天：二叉树
一、修剪二叉树（Leetcode 669） 递归法 class Solution:def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:# 如果当前节点为空，直接返回空节点（递归终止条件）if root is None:return None# 如果…...
KMP算法核心笔记：前后缀本质与nextval实现
KMP算法核心笔记：前后缀本质与nextval实现 核心疑问：为什么用「前后缀」而非「最大子串」？ 1. 结构唯一性 前后缀限定在字符串首尾区域，最大子串可位于任意位置只有前后缀能保证滑动后的有效对齐 2. 移动确定性 文本…...
Breeze 40A FOC 电调：Vfast 观测器技术赋能无人机精准动力控制
核心技术特性 1. 全新Vfast 观测器技术 基于先进矢量控制算法（FOC 驱动），实现电机状态实时精准观测，适配性优于传统 FOC 方案，兼容主流无人机动力配置。高效算法设计，输出功率与力效超越多数方波电调&…...
如何处理ONLYOFFICE文档服务器与Java Web应用间的安全认证和授权
如何处理ONLYOFFICE文档服务器与Java Web应用间的安全认证和授权？ 处理 ONLYOFFICE 文档服务器与 Java Web 应用之间的安全认证和授权，通常涉及以下几个关键步骤和技术： 1. JWT (JSON Web Token) 认证 启用 JWT： ONLYOFFICE 文档…...
手机上的PDF精简版：随时随地享受阅读
在移动互联网时代，随时随地阅读电子书和文档已经成为许多人的习惯。无论是学习、工作还是娱乐，一款好用的PDF阅读器都是必不可少的工具。今天，我们要介绍的 思读PDF精简版，就是这样一款简洁而强大的PDF阅读工具，能够让…...
XCTF-web（一）
view_source F12ctrluctrlshiftiURL前添加：view-source:curl http://192.168.1.1robots 根据题目提示，查看一下robots.txt /flag_ls_h3re.php backup /index.php.bak ┌──(kali㉿kali)-[~] └─$ cat index.php.bak <html> <…...
字节跳动开源 Godel-Rescheduler：适用于云原生系统的全局最优重调度框架
背景 在云原生调度中，一次调度往往无法解决所有问题，需要配合重调度来优化资源分配和任务摆放。传统的重调度框架主要集中在识别异常节点或任务，并通过迁移或删除来解决。然而，这些框架往往只能解决局部问题，无法提供…...
贪心算法day9（合并区间）
1.合并区间 56. 合并区间 - 力扣（LeetCode） 对于这种区间问题，我们应该先排序根据排序的结果总结一些规律，进而的得出解决该问题的策略。 class Solution {public static int[][] merge(int[][] intervals) {//第一步进行左端点…...
插件化设计，打造个性化音乐体验！
打工人们你们好！这里是摸鱼 特供版~ 今天给大家带来一款超酷的音乐播放器——MusicFree，它不仅功能强大，还支持插件化设计，让你的音乐体验更加个性化！ 推荐指数：★★★★★ 1. 插件化设计 功能强大&#…...
深入解析分类模型评估指标：ROC曲线、AUC值、F1分数与分类报告
标题：深入解析分类模型评估指标：ROC曲线、AUC值、F1分数与分类报告 摘要： 在机器学习中，评估分类模型的性能是至关重要的一步。本文详细介绍了四个核心评估指标：ROC曲线、AUC值、F1分数和分类报告。通过对比这些指标…...
2025第16届蓝桥杯省赛之研究生组F题01串求解
2025第16届蓝桥杯省赛之研究生组F题01串求解 一、题目概述二、解题思路2.1题目分析2.2解题思路 三、求解代码3.1求解步骤3.1.1求解x所在的二进制位数区间3.1.2求解总位数为cnt的含1数3.1.3求解cnt1~x之间的含1数 3.2完整代码3.3代码验证 四、小结 一、题目概述 给定一个由0,1,…...
【2-10】E1与T1
前言 之前我们简单介绍了人类从电话线思维到如今的数据报分组交换思维过渡时期的各种技术产物，今天我们重点介绍 E1/T1技术。 文章目录 前言1. 产生背景2. T13. E14. SONET4.1 OC-14.2 OC-3 及其它 5. SDH5.1. STM-1 6. SONET VS SDH后记修改记录 1. 产生背景 E1/…...
2025 年蓝桥杯 Java B 组真题解析分享
今年是我第二次参加蓝桥杯软件类Java B组的比赛，虽然赛前做了不少准备，但真正坐在考场上时，还是有种熟悉又紧张的感觉。蓝桥杯的题目一向以“基础创新”著称，今年也不例外，每道题都考验着我们对算法的理解、代码实现能…...
IMX6ULL2025年最新部署方案2在Ubuntu24.04上编译通过Qt5.12.9且部署到IMX6ULL正点原子开发板上
IMX6ULL2025年最新部署方案2:在Ubuntu24.04上编译通过Qt5.12.9且部署到IMX6ULL正点原子开发板上 前言 本篇方案部署是笔者这几天除了打蓝桥杯以外，笔者在研究的东西，现在写道这里的时候，笔者已经成功的在Ubuntu24.04上，使用默…...
通过微信APPID获取小程序名称
进入微信公众平台，登录自己的小程序后台管理端，在“账号设置”中找到“第三方设置” 在“第三方设置”页面中，将页面拉到最下面，即可通过appid获取到这个小程序的名称信息...
混合开发部署实战：PyInstaller + .NET 8 + Docker全链路配置
文章目录 一、PyInstaller打包Python环境1. 基础打包（Linux环境）2. 高级配置3. 验证打包结果 二、.NET 8与Python的集成模式1. 进程调用（推荐方案）2. REST API通信 三、Docker多阶段构建配置1. 完整Dockerfile示例2. 关键配置解析…...
使用 Sass 打造动态星空背景效果
在前端开发中，视觉效果越来越受到重视。本文将通过一个生动的示例，讲解如何利用 Sass 构建一个具有动态星空滚动效果的背景页面，同时也系统介绍 Sass 的核心功能与实践技巧。 一、Sass 的作用 Sass（Syntactically Awesome Style …...
低空经济有哪些GIS相关岗位?
在低空经济中，GIS（地理信息系统）技术发挥着重要作用。GIS开发工程师负责开发、维护和优化与低空经济相关的GIS系统，如无人机起降场布局、空域管理、气象监测等。一般会参与二、三维GIS项目数据处理与前端开发，以及相关…...
Python 垃圾回收机制全解析：内存释放与优化
在编写高效、稳定的 Python 程序时，内存管理往往是一个被忽视但至关重要的领域。对于 Python 开发者来说，最初的学习曲线通常集中在语法、库使用和应用框架上，而对于内存管理和垃圾回收（GC，Garbage Collection…...
性能优化实践
4.1 大规模量子态处理的性能优化 背景与问题分析 量子计算中的大规模量子态处理（如量子模拟、量子态可视化）需要高效计算和实时渲染能力。传统图形API（如WebGL）在处理高维度量子态时可能面临性能瓶颈，甚至崩溃（如表格中14量子比特时WebGL的崩溃）。而现代API（如WebGPU…...
opentelemetry笔记
span https://github.com/open-telemetry/opentelemetry-cpp/blob/f987c9c094f276336569eeea85f17e361de5e518/sdk/src/trace/span.h 在 OpenTelemetry C 的 sdk/src/trace 目录中，不同的 span 定义和实现是为了支持追踪（Tracing）功能的多样…...
【JavaScript】二十一、日期对象
文章目录 1、实例化日期对象2、相关方法3、时间戳4、案例：毕业🎓倒计时效果 1、实例化日期对象 获得当前时间 const date new Date()获得指定时间 const date new Date(2025-4-14 20:46:00) console.log(date)2、相关方法 方法作用说明getFullYear…...
GIT工具学习【1】：新安装git预操作
目录 1.写在前面2.为常用指令配置别名3.初始化4.解决中文乱码问题 1.写在前面 新安装git命令后，需要一些设置会用的比较的顺畅。 这篇文章只要跟着做即可，至于原理，后面会写清楚的。 2.为常用指令配置别名 #新建一个.bashrc touch ~/.bash…...
docker安装ES
ES安装步骤 1. 创建docker网络，使其docker内部通信 2. 下载 | 导入镜像文件（ES Kibana） 3. 创建容器，并访问 4. 安装Ik分词器（es对中文并不友好，所以需要安装IK分词使其适配中文） 1. 创建docke…...
【控制学】控制学分类
【控制学】控制学分类 文章目录 [TOC](文章目录) 前言一、工程控制论1. 经典控制理论2. 现代控制理论 二、生物控制论三、经济控制论总结 前言 控制学是物理、数学与工程的桥梁 提示：以下是本篇文章正文内容，下面案例可供参考 一、工程控制论 1. 经典…...
人工智能应用开发中常见的 工具、框架、平台 的分类、详细介绍及对比
以下是人工智能应用开发中常见的 工具、框架、平台 的分类、详细介绍及对比： 一、工具（Tools） 定义：用于完成特定任务的软件或库，通常专注于开发流程中的某个环节（如数据处理、模型调试、部署等ÿ…...
、Linux文件系统的校验(xfs_repair、fsck_ext4))
Linux磁盘格式化(mkfs、mkfs.xfs、mkfs.ext4)、Linux文件系统的校验(xfs_repair、fsck_ext4)
在Linux系统中，磁盘格式化和文件系统校验是系统管理的重要任务。以下是关键步骤和命令的总结： 磁盘格式化 1. 选择文件系统类型 XFS：适用于大文件和高并发场景，支持高性能和扩展性。ext4：成熟稳定的通用文件系统，适合大多数场景。2. 格式化命令 通用格式： sudo mkfs -…...
Android学习总结之git篇
Git 的原理时，你可以从数据结构、对象存储、引用管理、分支与合并等方面结合源码进行分析。以下是详细介绍： 1. 基本数据结构和对象存储 Git 底层主要基于四种对象来存储数据：blob（数据块）、tree（树&…...
Python基础语法——类型
目录 类型的意义动态类型静态类型 类型的意义 不同的类型,占用的内存空间是不同的. 占几个字节 int 默认是 4 个字节.动态扩容 float 固定 8 个字节 bool 一个字节就足够了 str 变长的 不同的类型,对应能够进行的操作也是不同的 int/float, “” “-” “ * ” “/”——不能使…...
vue2中基于el-select封装一个懒加载下拉框
需求 当下拉选项的数据量过大时，后端接口是分页格式返回数据。 解决方案 自定义封装一个懒加载下拉组件，每次滚动到底部时自动获取下一页数据，这样可有效防止数据量过大时造成组件卡顿。 具体实现步骤 1、创建懒加载下拉选择组件 <t…...
uniapp的h5，打开的时候，标题会一闪而过应用名称，再显示当前页面的标题
问题： 微信小程序，通过webview打开了uniapp创建的h5，但是打开h5时，会先显示h5的应用名称，然后才切换为该页面的标题。 过程： 查过很多资料，有说修改应用名称，有说设置navigationS…...
HarmonyOS 5 开发环境全解析：从搭建到实战
鸿蒙来了，从 1.0 到 5.0，它不再只是“华为的操作系统”，而是万物互联生态的核心驱动。作为开发者，你准备好拥抱这个全新时代了吗？ 你是否还在犹豫：HarmonyOS 5 开发门槛高不高？该用 DevEco Stu…...
2.2 函数返回值
1.回顾def def sum(x,y): return xy res sum(10,20) #调用函数 print(res) 2.函数的三个重要属性 -函数的类型：function -函数的ID：16进制的整数数值 -函数的值：封装在函数中的数据和代码 # - 函数是一块内存空间，通过…...
OpenAI发布GPT-4.1：开发者专属模型的深度解析 [特殊字符]
最近OpenAI发布了GPT-4.1模型，却让不少人感到困惑。今天我们就来深入剖析这个新模型的关键信息！ 重要前提：API专属模型 💻 首先需要明确的是，GPT-4.1仅通过API提供，不会出现在聊天界面中。这是因为该模型主…...
Cython中操作C++字符串
使用Cython开发Python扩展模块-CSDN博客中文末对python代码做了部分C优化，并提及未对字符串类型做优化，并且提到如果不是真正搞懂了C字符串的操作和Python的C API中与字符串相关的知识，最好不要动Python中的字符串类型。为了搞明白在Cython中…...
Dify插件内网安装，解决Dify1.x插件安装总失败问题，手把手教你暴力破解：从镜像源到二进制打包全攻略
背景 自从dify升级到1.0以后，所有的工具和模型都改成了插件化，需要进行插件的安装。在手撕Dify1.x插件报错！从配置到网络到Pip镜像，一条龙排雷实录 已经指出了dify在线安装插件的各种问题。 首发地址 在前面的几个版本中&…...
二极管详解：特性参数、选型要点与分类
一、二极管的基本定义 二极管（Diode） 是由半导体材料（如硅、锗）构成的双端器件，核心特性是单向导电性。其结构基于PN结，正向偏置导通，反向偏置截止。 核心功能： 整流（交…...
BufferedOutputStream 终极解析与记忆指南
BufferedOutputStream 终极解析与记忆指南 一、核心本质 BufferedOutputStream 是 Java 提供的缓冲字节输出流，继承自 FilterOutputStream，通过内存缓冲区显著提升 I/O 性能。 核心特性速查表 特性说明继承链OutputStream → FilterOutputStream → …...
Google政策大更新：影响金融，新闻，社交等所有类别App
Google Play 4月10日 迎来了2025年第一次大版本更新，新政主要涉及金融（个人贷款），新闻两个行业。但澄清内容部分却使得所有行业都需进行一定的更新。下面，我们依次从金融（个人贷款），…...
【Linux网络与网络编程】10.网络层协议IP
前言 我们之前谈的主机B把数据传递给主机C过程都是黑盒式的，即并没有考虑它的中间过程。本篇博客和下一篇博客将要考虑的问题是：主机B和主机C并不是直接连接的，主机B想要把数据传输给主机C需要经过若干路由器的。我们就引出了两个问题&#x…...
Docker 搭建 RabbitMQ
Docker 搭建 RabbitMQ 前言一、准备工作二、设置目录结构三、编写启动脚本四、Host 网络模式 vs Port 映射模式1. Host 网络模式2. Port 映射模式 五、端口配置对比六、配置示例七、查看与管理八、扩展与高可用九、常用命令 前言 在现代微服务与分布式架构中，Rabbi…...
浏览器自动化检测对抗：修改navigator.webdriver属性的底层实现
一、背景介绍：你被自动化检测拒之门外了吗？ 在使用 Selenium 或 Playwright 等浏览器自动化工具爬取数据时，经常会遇到「被检测」问题，尤其像 Amazon 这样反爬策略严密的网站。常见的检测机制之一就是检查 JavaScript 中的 navig…...
聊聊Spring AI Alibaba的DocumentParser
序 本文主要研究一下Spring AI Alibaba的DocumentParser DocumentParser spring-ai-alibaba-core/src/main/java/com/alibaba/cloud/ai/document/DocumentParser.java public interface DocumentParser {/*** Parses a given {link InputStream} into a {link Document}. T…...
用css给div列表加个序号
用 CSS 的 counter 相关属性来为列表添加序号。以下是具体的代码，我将以 HTML 文件的形式提供，并且会运行展示效果： .as-div {// counter-reset: my-counter; /* 计数器名称是my-counter */// counter-reset: small-apple; /* 计数器名称是s…...
CSS标签选择器与类选择器
CSS标签选择器 标签选择器（元素选择器）是最基本的选择器之一，用于选择HTML文档中的特定标签元素并应用样式。它使用HTML标签名称作为选择器，选择匹配该标签的所有元素。 作用：通过HTML标签名选择元素 以下是CSS标签选…...
（51单片机）LCD显示日期时间时钟（DS1302时钟模块教学）（LCD1602教程）
目录 源代码 main.c LCD1602.c LCD1602.h DS1302.c DS1302.h 代码解析与教程： LCD1602模块 DS1302模块 效果视频： 源代码 如上图将5个文放在Keli5 中即可，然后烧录在单片机中就行了 烧录软件用的是STC-ISP，不知道怎么安装的…...
编译原理（自考13007）
资源内容 大纲 概述...
C#Winform程序将子窗体嵌入容器方法
private void OpenForm(Form childFrom) { //首先判断容器中是否有其他的窗体 foreach (Control item in this.panelRight.Controls) { if (item is Form) { ((Form)item).Close(); } } //嵌入新的窗体 childFrom.TopLevel false;//将子窗体设置成非顶级控件 childFrom.Parent…...
WPS JS宏编程教程（从基础到进阶）-- 第八部分：字符串技术与WPS结合应用
目录 第8章 字符串技术与WPS结合应用8-1 字符串的3种引用方式场景：动态生成报表标题三种引用方式对比代码解析表模板字符串核心优势8-2 字符串处理之切片与搜索场景：提取身份证中的出生年份三大截取方法对比方法选择指南索引搜索实战8-3 字符串处理之修改与填充场景：规范商品…...
WPS Office安卓版文档编辑功能与兼容性评测【高效编辑】
一、界面设计与操作体验 WPS Office安卓版采用简洁直观的界面设计，首页默认展示近期文档列表，支持一键新建文档、表格或演示文稿。整体操作逻辑与PC端保持一致，新用户也能快速上手。编辑工具栏设计合理，常用功能如字体设置、段落…...