leetcode每日一练-第108题-将有序数组转换为二叉搜索树


一、思路
递归
二、解题方法
在给定中序遍历序列数组的情况下,每一个子树中的数字在数组中一定是连续的,因此可以通过数组下标范围确定子树包含的数字,下标范围记为 [left,right]。对于整个中序遍历序列,下标范围从 left=0到 right=nums.size()−1。当 left>right 时,平衡二叉搜索树为空。
选择中间位置左边的数字作为根节点
三、code
class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums,0,nums.size()-1);}TreeNode* helper(vector<int>& nums,int left,int right){if(left>right)//当左边界 left 大于右边界 right 时,意味着当前处理的区间为空,即没有元素可以用来构建子树了。这种情况下,我们返回 nullptr,表示当前子树为空树。{return nullptr;}int mid=(left+right+1)/2;//计算当前处理区间的中间位置,总是选择中间位置左边的数字作为根节点。这样可以保证构建的二叉搜索树是高度平衡的。TreeNode* root=new TreeNode(nums[mid]);//创建当前区间中间位置的元素值为根节点的二叉树节点。root->left=helper(nums,left,mid-1);//递归构建当前根节点的左子树,将左边界设为 left,右边界设为中间位置的前一个位置 mid - 1。root->right=helper(nums,mid+1,right);//递归构建当前根节点的右子树,将左边界设为中间位置的后一个位置 mid + 1,右边界设为 right。return root;}
};
=========================================================================学到的知识:
①
前序遍历(Preorder Traversal):在二叉树中,先访问根节点,然后按照左子树、右子树的顺序递归遍历子树。在前序遍历中,根节点的访问顺序是最先的。
中序遍历(Inorder Traversal):在二叉树中,先按照左子树、根节点、右子树的顺序递归遍历子树。在中序遍历中,根节点的访问顺序位于左右子树之间。
后序遍历(Postorder Traversal):在二叉树中,先按照左子树、右子树、根节点的顺序递归遍历子树。在后序遍历中,根节点的访问顺序是最后的。
这三种遍历方式是深度优先搜索(DFS)的三种不同变种。它们分别有不同的应用场景:
- 前序遍历:适用于需要先处理根节点再处理子节点的场景,比如复制整个树的结构或序列化为字符串。
- 中序遍历:适用于二叉搜索树,可以将其按从小到大的顺序输出,比如查找树中第 k 小的元素。
- 后序遍历:适用于释放二叉树的内存,先释放子节点再释放根节点,以防止访问已经释放的内存。
②TreeNode* root = new TreeNode(nums[mid]);
这行代码用于创建一个新的二叉树节点,并将其值初始化为有序数组中间位置的元素 nums[mid]
相关文章:
leetcode每日一练-第108题-将有序数组转换为二叉搜索树
一、思路 递归 二、解题方法 在给定中序遍历序列数组的情况下,每一个子树中的数字在数组中一定是连续的,因此可以通过数组下标范围确定子树包含的数字,下标范围记为 [left,right]。对于整个中序遍历序列,下标范围从 left0到 ri…...
王道《操作系统》学习(二)—— 进程管理(二)
2.1 处理机调度的概念、层次 2.1.1 调度的基本概念 2.1.2 调度的三个层次 (1)高级调度(作业调度) (2)中级调度(内存调度) 补充知识:进程的挂起状态和七状态模型 &#x…...
Vulnhub: shenron: 3靶机
kali:192.168.111.111 靶机:192.168.111.171 信息收集 端口扫描 nmap -A -sC -v -sV -T5 -p- --scripthttp-enum 192.168.111.171 修改hosts后访问目标80端口,发现是wordpress wpscan收集目标用户,爆破出密码:ilov…...
Kubernetes高可用集群二进制部署(二)ETCD集群部署
Kubernetes概述 使用kubeadm快速部署一个k8s集群 Kubernetes高可用集群二进制部署(一)主机准备和负载均衡器安装 Kubernetes高可用集群二进制部署(二)ETCD集群部署 Kubernetes高可用集群二进制部署(三)部署…...
mysql主从复制及原理
目录 主从复制原理实现主从复制 主从复制原理 主要基于MySQL二进制日志 主要包括三个线程(2个I/O线程,1个SQL线程) 1、MySQL将数据变化记录到二进制日志中; 2、Slave将MySQL的二进制日志拷贝到Slave的中继日志中; …...
MQTT服务器详细介绍:连接物联网的通信枢纽
随着物联网技术的不断发展,MQTT(Message Queuing Telemetry Transport)协议作为一种轻量级、可靠、灵活的通信协议,被广泛应用于物联网领域。在MQTT系统中,MQTT服务器扮演着重要的角色,作为连接物联网设备和…...
通过VBA宏合并Excel工作表
工作中经常会用到的把几个Excel文件合并到一个,或者是把一个Excel文件里的所有Sheet合并到一个Sheet来进行统计。下面分别提供用vba宏来解决这两个问题的方法。 1、合并Excel文件 打开一个空Excel文件,AltF11,插入一个模块,开始…...
Mac 定时重启 TouchBar 脚本(缓解闪烁问题)
背景 Mac 笔记本 TouchBar 是真的脆啊,合盖使用一段时间就废了,右侧一直闪烁简直亮瞎眼 😂 经过观察,总结出闪烁规律如下: 工作状态:不断操作电脑时,触控栏处于工作状态,几乎不闪…...
Redis主从复制、哨兵机制、集群分片
目录 一.主从复制 1.概述 2.主从架构相比于单点架构的优势 3.主从复制原理和工作流程 第一次同步 第一阶段:建立链接、协商同步 第二阶段:主服务器同步数据给从服务器 第三阶段:主服务器发送新写操作命令给从服务器 基于长连接的命…...
字段填充策略 FieldFill
实体类中有如下属性,通过上面的自动填充属性,我们可以实现在进行插入(insert)操作时对添加了注解TableField(fill FieldFill.INSERT)的字段进行自动填充(解释:后面会写配置自动填充的配置类,该…...
Docker run 启动容器报错
今天在Windows下启动docker容器发现的三个错误: Ports are not available: exposing port TCP 0.0.0.0:1521 -> 0.0.0.0:0: listen tcp 0.0.0.0:1521: bind: Only one usage of each socket address (protocol/network address/port) is normally permitted. 端口…...
Golang之路---03 面向对象——类型断言
类型断言 作用 检查 i 是否为 nil检查 i 存储的值是否为某个类型 使用方式 第一种: t : i.(T)这个表达式可以断言一个接口对象(i)里不是 nil,并且接口对象(i)存储的值的类型是 T,如果断言成…...
Atcoder 做题记录
My OI Blog A R C 155 F \mathbb{ARC \ 155 \ F} ARC 155 F E, F 先咕着,做一些多项式题,这篇题解是我人工翻译的 [1] Double Counting 双重计数 考虑从叶子节点开始,用唯一的方式(如果有的话)来构造出一棵满足条件的树…...
C++之观察者模式(发布-订阅)
目录 模式简介 介绍 优点 缺点 代码实现 场景说明 实现代码 运行结果 模式简介 观察者模式(Observer Pattern),也叫我们熟知的发布-订阅模式。 它是一种行为型模式。 介绍 观察者模式主要关注的是对象的一对多的关系, …...
无头单链表,有完整测试程序
🍟无头单链表 👻无头单链表的所有结点都存储有效信息 👻无头单链表相对带头单链表,在有些涉及更改头节点的函数上需要传二级指针 🍟头文件list.h #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #includ…...
2023年第四届“华数杯”数学建模思路 - 案例:FPTree-频繁模式树算法
## 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法,就是频繁模式树算法,他与Apriori算法一样也是用来挖掘频繁项集的,…...
MySQL做分布式锁
分布式锁mysql实现方式 方式1:唯一索引 创建锁表,内部存在字段表示资源名及资源描述,同一资源名使用数据库唯一性限制。多个进程同时往数据库锁表中写入对某个资源的占有记录,当某个进程成功写入时则表示其获取锁成功其他进程由于…...
Python学习笔记:变量类型、字符串基本操作
1.注释 单行注释 # 单行注释 多行注释 """ 多行注释 """2.变量类型 # 基本变量类型 a 1 # integer b 1.5 # float c string # String d "string" # string e False # boolean # list\tuple\dictionar…...
JVM的组件、自动垃圾回收的工作原理、分代垃圾回收过程、可用的垃圾回收器类型
详细画的jvm模型图 https://www.processon.com/diagraming/64c8aa11c07d99075d934311 官方网址 https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/gc01/index.html 相关概念 年轻代是所有新对象被分配和老化的地方。当年轻代填满时,这会导致m…...
【elementui】解决el-select组件失去焦点blur事件每次获取的是上一次选中值的问题
目录 【问题描述】 【问题摘要】 【分析问题】 【完整Test代码】 【封装自定义指令】 ↑↑↑↑↑↑↑↑↑↑↑↑ 不想看解决问题过程的可点击上方【封装自定义指令】目录直接跳转获取结果即可~~~ 【问题描述】 一位朋友遇到这么一个开发场景:在表格里面嵌入el-…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式
pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图,如果边框加在dom上面,pdf-lib导出svg的时候并不会导出边框,所以只能在echarts图上面加边框 grid的边框是在图里…...
