代码随想录|Day20|二叉树09|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树
思路:利用二叉搜索树的性质,对于每个节点,判断其是否在区间内:
- 如果节点值 < low,则此节点和其左子树都不在范围内
- 如果节点值 > high,则此节点和其右子树都不在范围内
- 如果 low < 节点值 < high,则保留此节点,但需要递归修建其左右子树
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return None# 如果节点小于low,返回右子树修剪的结果if root.val < low:return self.trimBST(root.right, low, high)# 如果节点大于high,返回左子树修剪的结果elif root.val > high:return self.trimBST(root.left, low, high)# 如果节点在区间内,递归修建左右子树else:root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root
108.将有序数组转换为二叉搜索树
思路:我们知道,按照中序遍历一个二叉搜索树将获得一个递增数组。因此我们可以将数组二分,中间元素所谓根节点,左边元素作为左子树,右边元素作为右子树,递归下去可以构成平衡二叉搜索树。
class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:def helper(left, right):if left > right:return Nonemid = (left + right) // 2root = TreeNode(nums[mid])root.left = helper(left, mid - 1)root.right = helper(mid + 1, right)return rootreturn helper(0, len(nums)-1)
538.把二叉搜索树转换为累加树
什么是累加树?
指在二叉搜索树(BST)的基础上进行转换得到的一种特殊形式的树。在累加树中,每个节点的值被替换为原始二叉搜索树中所有大于该节点值的节点值之和加上该节点自身的值。
思路:我们从最大值开始累加,因此遍历顺序是元素从大到小。我们可以使用反向中序遍历来实现:右中左。
class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.sum = 0def traverse(node):if not node:return# 反向中序遍历:右 -> 根 -> 左traverse(node.right)self.sum += node.valnode.val = self.sumtraverse(node.left)traverse(root)return root相关文章:
代码随想录|Day20|二叉树09|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树 思路:利用二叉搜索树的性质,对于每个节点,判断其是否在区间内: 如果节点值 < low,则此节点和其左子树都不在范围内如果节点值 > high,则此节点和其右子树都不在范围内如果 low &…...
开源的java 代码分析库介绍
本文将为您详细讲解开源的 Java 代码分析库,以及如何安装这些库、它们的特性、区别和应用场景。Java 社区提供了多种代码分析工具,这些工具可以帮助您在 Java 应用程序中进行代码质量评估、性能分析、安全检查等功能。 1. CheckStyle 安装 - 通过…...
基于udp协议的网络通信(windows客户端版+简易聊天室版),重定向到终端
目录 和windows通信 引入 思路 WSADATA 代码 运行情况 简单的聊天室 思路 重定向 代码 terminal.hpp -- 重定向函数 服务端 客户端 运行情况 和windows通信 引入 linux和windows都需要联网,虽然他们系统设计不同,但网络部分一定是相同的,所以套接字也是一样的 这…...
Qt+FFmpeg+opengl从零制作视频播放器-7.OpenGL播放视频
在上一节Qt+FFmpeg+opengl从零制作视频播放器-6.视频解码中,我们学到了如何将视频数据解码成YUV原始数据,并且保存到本地,最后使用工具来播放YUV文件。 本节使用QOpenGLWidget来渲染解码后的YUV视频数据。 首先简单介绍QOpenGLWidget的使用。 QOpenGLWidget类是用于渲染O…...
用两个栈实现简单的四则运算
题目要求:给定一个字符串如“12*3”,没有括号,要求利用栈的知识来处理结果算出答案 我的思路:建立两个栈,一个存放数据,一个存放符号,再定义一个结构体做为操作的主体,然后制作几个函数&#x…...
<个人笔记>数论
1.快速幂 (1)求解问题: 给定 n组 ai,bi,pi求 aibi mod pi 的值。 (2)主要思想:任何一个数(b),可以被 n 个 2k 相加获得。 即 b 2k1 2k2 2k3 … 2logb。 快速幂模板: typedef long long LL;LL qmi(int a,int b,int p){LL re…...
CMS垃圾收集
初始标记 需要暂停所有的其他线程,但这个阶段会很快完成。它的目的是标记所有的根对象,以及被根对象直接引用的对象,以及年轻代指向老年代的对象,不会遍历对象关系,单线程执行。 并发标记阶段 不需要暂停应用线程&a…...
Incorrect DECIMAL value: ‘0‘ for column ‘‘ at row -1
用mysql插入数据的时候,报了上面的错误。 语句类似:INSERT INTO t_aa(c1,c2,c3,a1,a2,a3) SELECT t1,t2,t3,b1,b2,b3 FROM ( SELECT, t1,t2,t3 cast(ifnull(d1,0)as decimal(8,1) b1, cast(ifnull(d2,0) as decimal(8,1) b2, …...
Vue3组件通信的方式
1、父给子传 — props 父组件 <template><h1>父</h1><Son :value"number" /><button click"add">点我加1</button> </template><script setup> import Son from ./son.vue;import { ref } from vue; le…...
双场板功率型GaN HEMT中用于精确开关行为的电容建模
来源:Capacitance Modeling in Dual Field-Plate Power GaN HEMT for Accurate Switching Behavior (TED 16年) 摘要 本文提出了一种基于表面电势的紧凑模型,用于描述具有栅极和源极场板(FP)结构的AlGaN/GaN高电子迁移率晶体管(…...
UE4_AI_行为树_行为树快速入门指南
声明:学习笔记。 在 行为树快速入门指南 中,你将学会如何创建一个敌方AI,该AI看到玩家后会做出反应并展开追逐。当玩家离开视线后,AI将在几秒钟后(这可根据你的需求进行调整)放弃追逐,并在场景中…...
c++ 面试100个题目中的编程题目
88、下列程序的运行结果是? #include <stdlib.h> #include <stdio.h> #include <string.h> #include <iostream> const char* str = "vermeer"; using namespace std; int main(){ const char* pstr = str;cout << "The add…...
C++初阶:类与对象(尾篇)
目录 1. 构造函数与初始化列表1.1 对象的创建与构造函数的初始化1.2 初始化列表及构造函数存在的意义1.3 explicit关键字与构造函数的类型转换 2. static成员变量与static成员函数2.1 static成员变量2.2 static成员函数 3. 日期类流插入操作符的重载与友元3.1 友元3.2 友元函数…...
Spring状态机简单实现
一、什么是状态机 状态机,又称有限状态自动机,是表示有限个状态以及在这些状态之间的转移和动作等行为的计算模型。状态机的概念其实可以应用的各种领域,包括电子工程、语言学、哲学、生物学、数学和逻辑学等,例如日常生活中的电…...
WebServer -- 面试题(下)
👂 夏风 - Gifty - 单曲 - 网易云音乐 目录 🌼前言 🎂面试题(下) 4)HTTP报文解析 为什么要用状态机 状态转移图画一下 https 协议为什么安全 https 的 ssl 连接过程 GET 和 POST 的区别 5)数据库注册登录 登…...
企业微信如何接入第三方应用?
1.登录企业微信管理后台:https://work.weixin.qq.com/wework_admin 2.点击创建应用; 3. 此时可以看到已经创建好的应用,并且生成应用的唯一id(agentId) 4. 第三方应用申请域名 (举例&…...
JAVA后端编码的主键字段存储为什么倾向于使用雪花算法
1.背景 最近有人问,什么是雪花算法,为什么使用雪花算法不使用数据库UUID,基于此,写一个说明。 2.简介 (1)雪花算法,英文名为snowflake,翻译过来就是是雪花,所以叫雪花…...
Rust 深度学习库 Burn
一、概述 Burn 它是一个新的综合动态深度学习框架,使用 Rust 构建的,以极高的灵活性、计算效率和可移植性作为其主要目标。 Rust Burn 是一个以灵活性、高性能和易用性为核心设计原则工具,主打就是灵活性 、高性能 及易用性。 二、Rust B…...
C语言-存储期2.0
静态存储期 在数据段中分配的变量,统统拥有静态存储期,因此也都被称为静态变量。这里静态的含义,指的是这些变量的不会因为程序的运行而发生临时性的分配和释放,它们的生命周期是恒定的,跟整个程序一致。 静态变量包含…...
计算机网络面经八股-HTTP请求报文和响应报文的格式?
请求报文格式: 请求行(请求方法URI协议版本)请求头部空行请求主体 请求行:GET /sample.jsp HTTP/1.1 表示使用 GET 方法请求 /sample.jsp 资源,并使用 HTTP/1.1 协议。请求头部:包含多个字段,…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
