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

力扣二叉树--第四十一天

前言

写完这三道题,二叉树部分就先告一段落了。其实还有很多模糊的地方。

内容

一、修剪二叉搜索树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

递归
func trimBST(root *TreeNode, low int, high int) *TreeNode {if root==nil{return root}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
}
迭代
func trimBST(root *TreeNode,low,high int)*TreeNode{// 处理 root,让 root 移动到[low, high] 范围内,注意是左闭右闭for root!=nil&&(root.Val<low||root.Val>high){if root.Val<low{root=root.Right}else{root=root.Left}}if root==nil{return nil}//必须在这里先判断// 此时 root 已经在[low, high] 范围内,处理左孩子元素小于 low 的情况(左节点是一定小于 root.Val,因此天然小于 high)for node:=root; node.Left!=nil;{if node.Left.Val<low{node.Left=node.Left.Right}else{node=node.Left}}// 此时 root 已经在[low, high] 范围内,处理右孩子大于 high 的情况for node:=root; node.Right!=nil;{if node.Right.Val>high{node.Right=node.Right.Left}else{node=node.Right}}return root
}
二、将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

递归
func sortedArrayToBST(nums []int) *TreeNode {if len(nums)==0{//终止条件return nil}mid:=len(nums)/2root:=&TreeNode{Val:nums[mid],}root.Left=sortedArrayToBST(nums[:mid])root.Right=sortedArrayToBST(nums[mid+1:])return root
}
 三、把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。
反序中序遍历
func convertBST(root *TreeNode) *TreeNode {sum:=0var dfs func(*TreeNode)dfs=func(node *TreeNode){if node!=nil{dfs(node.Right)sum+=node.Valnode.Val=sumdfs(node.Left)}}dfs(root)return root
}

最后

写个总结吧。下一站,回溯算法!

相关文章:

力扣二叉树--第四十一天

前言 写完这三道题&#xff0c;二叉树部分就先告一段落了。其实还有很多模糊的地方。 内容 一、修剪二叉搜索树 669. 修剪二叉搜索树 给你二叉搜索树的根节点 root &#xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[l…...

计算机视觉(P2)-计算机视觉任务和应用

一、说明 在本文中&#xff0c;我们将探讨主要的计算机视觉任务以及每个任务最流行的应用程序。 二、图像内容分类 2.1. 图像分类 图像分类是计算机视觉领域的主要任务之一[1]。在该任务中&#xff0c;经过训练的模型根据预定义的类集为图像分配特定的类。下图是著名的CIFAR…...

redis-学习笔记(Jedis zset 简单命令)

zadd & zrange zadd , 插入的第一个参数是 zset , 第二个参数是 score, 第三个参数是 member 成员 内部依据 score 排序 zrange 返回 key 对应的 对应区间内的值 zrangeWithScore 返回 key 对应的 对应区间内的值和分数 示例代码 zcard 返回 key 对应的 zset 的长度 示例代…...

uniapp实战 —— 弹出层 uni-popup (含vue3子组件调父组件的方法)

效果预览 弹出的内容 src\pages\goods\components\ServicePanel.vue <script setup lang"ts"> // 子组件调父组件的方法 const emit defineEmits<{(event: close): void }>() </script><template><view class"service-panel"…...

智能优化算法应用:基于平衡优化器算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于平衡优化器算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于平衡优化器算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.平衡优化器算法4.实验参数设定5.算法…...

Netty详细文档

Netty教程 文章目录 Netty教程 Netty简介Netty 的介绍Netty 的应用场景互联网行业游戏行业大数据领域其它开源项目使用到 Netty Netty 的学习资料参考 Java BIO编程I/O 模型BIO、NIO、AIO 使用场景分析Java BIO 基本介绍Java BIO 工作机制Java BIO 应用实例问题分析 Java NIO编…...

C语言结构体和位段

自定义类型&#xff1a;结构体及联合和枚举 一.结构体类型的声明1.1 结构体的概念1.2结构的声明1.3特殊的声明1.4结构体的自引用1.5可以使用typedef重命名 二.结构体变量的创建和初始化2.1结构体变量的初始化使用{}2.2初始化&#xff1a;定义变量的同时赋初值。2.3结构体嵌套及…...

【剑指offer|图解|数组】寻找文件副本 + 螺旋遍历二维数组

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;数据结构、剑指offer每日一练 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 一. ⛳️寻找文件副本(题目难度&#xff1a;简单)1.1 题目1.2 示例1.3 限制1.4 解题思路一c代…...

Python核心编程之文件和输入输出

目录 一、文件对象 二、 文件内建函数[open()和file()] 1、工厂函数 file() 2、通用换行符支持(UNS)...

Axure 9基本元件,表单及表格元件简介,表单案例

目录 一.基本元件 1.元件基本介绍 2.基本元件的使用 二.表单及表格元件 三.表单案例 四.简单简历绘制 一.基本元件 1.元件基本介绍 概述 - 在Axure RP中&#xff0c;元件是**构建原型图的基础模块**。 将元件从元件库里拖拽到画布中&#xff0c;即可添加元件到你的原型…...

ARM I2C通信

1.概念 I2C总线是PHLIPS公司在八十年代初推出的一种串行的半双工同步总线&#xff0c;主要用于连接整体电路2.IIC总线硬件连接 1.IIC总线支持多主机多从机&#xff0c;但是在实际开发过程中&#xff0c;大多数采用单主机多从机模式 2.挂接到IIC总线上&#xff0c;每个从机设备都…...

Cent OS7 磁盘挂载:扩展存储空间和自动挂载

文章目录 &#xff08;1&#xff09;概述&#xff08;2&#xff09;查看磁盘使用情况&#xff08;3&#xff09;VMware虚拟机挂载磁盘&#xff08;4&#xff09;物理机磁盘挂载&#xff08;5&#xff09;ntfs硬盘处理 &#xff08;1&#xff09;概述 在Linux系统中&#xff0c…...

《使用ThinkPHP6开发项目》 - 创建应用

《使用ThinkPHP6开发项目》 - 安装ThinkPHP框架-CSDN博客 《使用ThinkPHP6开发项目》 - 设置项目环境变量-CSDN博客 《使用ThinkPHP6开发项目》 - 项目使用多应用开发-CSDN博客 根据前面的步骤&#xff0c;我们现在就可以开发我们的项目开发了&#xff0c;根据项目开发的需要…...

SpringBoot进行自然语言处理,利用Hanlp进行文本情感分析

. # &#x1f4d1;前言 本文主要是SpringBoot进行自然语言处理&#xff0c;利用Hanlp进行文本情感分析&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风…...

MySQL 报错 You can‘t specify target table for update in FROM clause解决办法

You can’t specify target table for update in FROM clause 其含义是&#xff1a;不能在同一表中查询的数据作为同一表的更新数 单独执行复合查询是正常的&#xff0c;如下&#xff1a; 但是当执行子查询删除命令时&#xff0c;报如下错误 DELETE FROM abpusers WHERE Id I…...

Linux中使用podman管理容器

本章主要介绍使用podman管理容器 了解什么是容器&#xff0c;容器和镜像的关系安装和配置podman拉取和删除镜像给镜像打标签导出和导入镜像创建和删除镜像数据卷的使用管理容器的命令使用普通用户管理容器 对于初学者来说&#xff0c;不太容易理解什么是容器&#xff0c;这里…...

飞天使-linux操作的一些技巧与知识点3-http的工作原理

文章目录 http工作原理nginx的正向代理和反向代理的区别一个小技巧dig 命令巧用 http工作原理 http1.0 协议 使用的是短连接&#xff0c;建立一次tcp连接&#xff0c;发起一次http的请求&#xff0c;结束&#xff0c;tcp断开 http1.1 协议使用的是长连接&#xff0c;建立一次tc…...

微搭低代码实现登录注册功能

目录 1 创建用户数据源2 实现登录逻辑3 搭建登录页面4 设置登录框5 实现登录的逻辑6 用户注册总结 原来产品在创建应用的时候可以创建模型应用&#xff0c;模型应用对应我们小程序的后端。最新的更新已经将模型应用的能力下线&#xff0c;那我们不得不自己实现一下后端的逻辑。…...

使用Cobalt Srike制作钓鱼文件

钓鱼 钓鱼文件是一种常见的网络攻击手段&#xff0c;旨在欺骗用户&#xff0c;诱使他们点击恶意链接、下载恶意附件或提供敏感信息。钓鱼文件的概念是通过伪装成合法、可信的文件或链接来欺骗受害者&#xff0c;使其相信文件或链接的来源是可信的&#xff0c;从而促使他们采取…...

任意文件读取漏洞

使用方法php://filter/readconvert.base64-encode/resourcexxx 任意文件读取漏洞 php://filter/readconvert.base64-encode/resourceflag 在url后边接上 以base64的编码形式 读取flag里面的内容 php://filter/readconvert.base64encode/resourceflag 用kali来解码 创建一个文…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...