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

leetcode108：将有序数组转化为二叉搜索树

news 来源：原创 2025/7/19 7:15:52

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵

平衡

二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

为了更好地解决这个问题并提供全面的解答，下面我将对任务进行逐步分析，详细解释每个步骤。我们将深入探讨如何将一个升序排列的整数数组转换为平衡二叉搜索树（Balanced Binary Search Tree, BST）。

问题概述

给定一个升序排列的整数数组 nums，我们需要将其转换为一棵平衡二叉搜索树。平衡二叉搜索树是一棵满足以下条件的二叉树：

每个节点的左子树和右子树的高度差不超过1（即平衡）。
每个节点的左子树的值小于该节点的值，而右子树的值大于该节点的值。

步骤1：详细定义题目的计算问题性质

我们需要明确题目中的计算问题性质，并分析其中的输入输出条件和潜在的边界条件。

输入

nums：一个整数数组，长度 n 满足 1 <= nums.length <= 10^4。
nums 中的元素按照严格升序排列，即 nums[i] < nums[i+1]。

输出

输出需要返回一棵平衡的二叉搜索树。
树中的节点值应保持与输入数组中的值一致，并且节点顺序必须符合二叉搜索树的性质。

边界条件

当数组长度为1时，输出的树应只有一个节点。
当数组长度为2时，输出的树可以有两个节点（左子树或右子树）。
数组的长度最大为10,000，意味着需要设计一个时间复杂度为O(n)的算法。

步骤2：分解题目并给出详细的解决思路

我们可以通过以下步骤来解决问题：

分析算法思路

这道题本质上要求我们在升序数组上构建一棵平衡的二叉搜索树。为了保持平衡，可以选择将数组的中间元素作为树的根节点。具体步骤如下：

递归构建树：从数组中选择中间元素作为根节点。然后递归地将左半部分数组（中间元素左侧）构建为左子树，右半部分数组（中间元素右侧）构建为右子树。

这意味着我们可以通过递归来分治问题，逐步构建出平衡二叉搜索树。
递归函数设计：我们可以定义一个递归函数，接受一个数组的子区间（由 left 和 right 索引表示），每次选择中间元素作为根节点，并继续递归地构建左右子树。

算法设计

递归步骤：假设当前子数组为 nums[left...right]，我们选择 mid = (left + right) // 2 作为根节点。然后递归地对 nums[left...mid-1] 和 nums[mid+1...right] 进行相同的操作，直到区间为空。
时间复杂度：
- 每次递归时，我们从当前区间中选择一个中间元素作为根节点，划分成两个子区间。
- 由于每个元素仅被访问一次，整个树的构建过程的时间复杂度是 O(n)，其中 n 是数组的长度。
空间复杂度：
- 递归调用栈的最大深度为树的高度，即 O(log n)，因此空间复杂度为 O(log n)。

实现细节

在 C++ 中，我们需要构建一个树节点类 TreeNode，该类包含值、左子树指针和右子树指针。

步骤3：C++代码实现


// 定义树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 递归构建平衡二叉搜索树的函数
TreeNode* sortedArrayToBSTHelper(const vector<int>& nums, int left, int right) {if (left > right) {return nullptr;}// 选择中间元素作为根节点int mid = left + (right - left) / 2;TreeNode* root = new TreeNode(nums[mid]);// 递归构建左子树和右子树root->left = sortedArrayToBSTHelper(nums, left, mid - 1);root->right = sortedArrayToBSTHelper(nums, mid + 1, right);return root;
}// 主函数：将数组转换为平衡二叉搜索树
TreeNode* sortedArrayToBST(const vector<int>& nums) {return sortedArrayToBSTHelper(nums, 0, nums.size() - 1);
}// 中序遍历函数，用于输出树的结构
void inorderTraversal(TreeNode* root) {if (root == nullptr) return;inorderTraversal(root->left);cout << root->val << " ";inorderTraversal(root->right);
}

代码解析

TreeNode结构体：用于表示二叉树的节点，包括一个整数值 val 和指向左右子节点的指针。
sortedArrayToBSTHelper函数：递归构建树的核心函数。每次选择中间元素创建树节点，并递归地构建左、右子树。
sortedArrayToBST函数：这是入口函数，调用 sortedArrayToBSTHelper 来构建整个树。
inorderTraversal函数：中序遍历函数，用于验证树的结构是否正确（因为平衡二叉搜索树的中序遍历应该是升序排列的）。

步骤4：从解题中总结启发

通过解决这个问题，我们可以总结出以下启发：

分治策略：该问题可以通过分治法来解决。每次选择数组的中间元素作为根节点，这是一种典型的递归问题，通过递归地分解问题来构建树。
平衡树的构建：通过确保每次选择中间元素，我们能够保证树的平衡性，使得左右子树的高度差最小，从而避免树的退化。
递归优化：递归是解决此类树问题的常见手段，关键在于如何合理划分问题的规模，并将问题简化到基本情况。

步骤5：探讨该算法的实际应用场景

平衡二叉搜索树（如 AVL 树、红黑树）在多个行业中有广泛的应用，特别是在需要高效查找、插入和删除操作的场景中。以下是几个实际应用示例：

数据库索引：数据库系统经常使用平衡二叉搜索树来实现索引，这样可以在O(log n)的时间复杂度内查找数据。
操作系统调度：在操作系统中，平衡二叉搜索树可以用于管理进程队列，以实现优先级调度。
网络路由：在计算机网络中，路由器可以使用平衡树来存储路由表，并实现快速的路由查找。

通过合理设计和应用平衡二叉搜索树，可以在许多需要快速查找、插入和删除操作的应用中大大提高性能。

leetcode108：将有序数组转化为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。示例 1： 输入：nums [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确…...

编程日记 2025/7/19 7:15:52

rust学习-初识rust

rust学习-初识rust 什么是 Rust？Rust 的特点什么是 Cargo？Cargo 的主要功能使用 Cargo 创建和管理项目Cargo.toml 文件详解常用 Cargo 命令什么是 Rustup？Rustup 的主要功能安装 Rustup验证安装使用 Rustup 管理工具链使用 Rustup 管理目标平…...

编程日记 2025/7/19 7:01:57

word怎么添加链接，点击直接到参考文献

word怎么添加链接，点击直接到参考文献有时候并不一定非得latex https://download.csdn.net/download/qq_38998213/90199214 在Word中添加点击可直接跳转到参考文献的链接，主要有以下两种方法：使用交叉引用和超链接结合的方法插入参考文献：首先，在文档中需要插入参考…...

编程日记 2025/7/19 7:03:34

数字赋能：制造企业如何靠“数字能力”实现可持续“超车”？

如今，制造业数字化转型可是个热门话题，全球都在积极推进。我国更是出台了一系列给力的政策来助力制造业数字化转型，像《中国制造 2025》就明确提出要加快制造业数字化、网络化、智能化发展，各省市也纷纷响应，从资金、税…...

编程日记 2025/7/19 7:04:16

C++——deque的了解和使用

目录引言标准库中的deque 一、deque的基本概念二、deque的常用接口 1.deque的迭代器 2.deque的初始化 3.deque的容量操作 3.1 有效长度和容量大小 3.2 有效长度和容量操作 4.deque的访问操作 5.deque的修改操作三、deque的应用场景结束语引言在C中&#x…...

编程日记 2025/7/16 9:01:29

vue使用el-select下拉框自定义复选框

在 Vue 开发中，高效且美观的组件能极大地提升用户体验和开发效率。在vue中使用elementplus 的 el-select下拉框实现了一个自定义的多选下拉框组件。一、代码功能概述这段代码创建了一个可多选的下拉框组件，通过el-select和el-checkbox-group结合的方…...

编程日记 2025/7/17 13:39:18

《探秘开源大模型：AI 世界的“超级引擎”》

《探秘开源大模型：AI 世界的“超级引擎”》一、开源大模型崛起之路二、开源大模型发展历程回顾（一）早期奠基：理论突破与初步实践（二）快速发展：百花齐放的模型格局（三）当下态势：走向成熟与多元融合三、开源大模型核心技术剖析（一）Transformer 架构：基石之稳（二）…...

编程日记 2025/7/19 1:31:32

浏览器跨域原因及解决方式

一、为什么会有跨域浏览器的同源策略用于限制一个源的文档或它所加载的脚本如何能与另一个源交互。它能帮助阻隔恶意文档，减少可能被攻击的媒介二、什么是同源两个url，只要它们的协议、域名、端口有一个不相同，就会导致跨域&#xf…...

编程日记 2025/7/14 1:36:23

如何解决Eigen和CUDA版本不匹配引起的错误math_functions.hpp: No such file or directory

Apollo9针对RTX40的docker环境里的Eigen库版本是3.3.4，CUDA是11.8: 编译我们自己封装模型的某些component代码时没问题，编译一个封装occ模型的component代码时始终报错: In file included from /usr/include/eigen3/Eigen/Geometry:11:0, …...

编程日记 2025/7/18 7:38:16

[服务器][教程]Ubuntu24.04 Server开机自动挂载硬盘教程

1. 查看硬盘ID ls -l /dev/disk/by-uuid可以看到对应的UUID所对应的分区 2. 创建挂载文件夹创建好文件夹即可 3. 修改配置文件 sudo vim /etc/fstab把对应的UUID和创建的挂载目录对应即可其中# Personal mount points下面的是自己新添加的 ：分区定位&#xff…...

编程日记 2025/7/14 5:32:06

idea项目导入gitee 码云

1、安装gitee插件 IDEA 码云插件已由 gitosc 更名为 gitee。 1 在码云平台帮助文档http://git.mydoc.io/?t153739上介绍的很清楚，推荐前两种方法， 搜索码云插件的时候记得名字是gitee，gitosc已经搜不到了。 2、使用码云托管项目如果之…...

编程日记 2025/7/15 0:37:10

前端页面展示本电脑的摄像头，并使用js获取摄像头列表

可以通过 JavaScript 使用 navigator.mediaDevices.enumerateDevices() 获取电脑上的摄像头列表。以下是一个示例代码，可以展示摄像头列表并选择进行预览。 HTML JavaScript 实现摄像头列表展示和预览 <!DOCTYPE html> <html lang"zh-CN">…...

编程日记 2025/7/17 21:42:18

小米自研vela系统kvdb数据库的使用（一）

KVDB数据库介绍 KVDB 数据库详细介绍KVDB 的基本原理 KVDB 的应用场景1. 缓存系统2. 配置管理3. 会话存储与用户状态管理4. 实时数据处理5. 日志记录与事件存储6. 分布式存储 KVDB 的作用KVDB 数据库的典型实现1. LevelDB2. RocksDB3. LMDB (Lightning Memory-Mapped Database)…...

编程日记 2025/7/14 8:11:51

Python 中的 `iter` 函数

因为在jax的代码接触了这个函数，不是很熟悉，每次看见名字只知道是迭代但是不知道是怎么迭代，因此写下以下笔记提醒自己。 def iter(source, sentinelNone): # known special case of iter"""iter(iterable) -> iteratorit…...

编程日记 2025/7/15 23:58:00

【AIGC】电话录音转文字实践：基于Google Cloud Speech-to-Text-v1的技术方案Python

引言在当今数字化时代，将语音内容转换为文字已经成为一个非常重要的技术需求。无论是客服通话记录、会议纪要，还是电话采访内容，高效准确的语音转文字服务都能大大提升工作效率。本文将详细介绍如何利用Google Cloud Speech-to-Text服务实现…...

编程日记 2025/7/18 18:29:17

《AI赋能自由职业：开启竞争力提升新征程》

在当今数字化时代，AI技术为自由职业者带来了前所未有的机遇，使其能够在激烈的市场竞争中脱颖而出。以下是自由职业者借助AI提升自身竞争力的几种方法。利用AI优化工作流程，提高效率自动化任务处理：自由职业者可以借助自动化工具…...

编程日记 2025/7/14 1:32:53

学习vue3的笔记

一、vue和react的对比 1、基础介绍 vue：https://cn.vuejs.org/ vue3是2020年创建的 react：https://react.dev/ react是一个2013年开源的JavaScript库，严格意义上来说不是一个框架 2、diff算法两个框架采用的都是同级对比策略两节点对…...

编程日记 2025/7/15 11:32:08

为什么要用ZGC

一、为什么要用 ZGC 问题我们有个“智慧园区”的项目,我们的下游系统“交叉带”[硬件系统]要求我们服务 60ms内返回结果，并且可用性要达到 99.99%。当时使用的是 G1垃圾回收器，单次 Young GC 40ms，一分钟10次，接口平均响应时间…...

编程日记 2025/7/18 23:59:34

rm误删掉的文件夹/文件如何恢复

Linux环境rm不小心误删掉文件/文件夹如何安全恢复，推荐tool：ext4magic(ext4 or ext3)，大家如果遇到误删的，希望可以帮到你。误删了，最好要保留现场，如果能umout当前分区最好，不要在当前磁盘分…...

编程日记 2025/7/15 17:10:39

uniapp - 小程序实现摄像头拍照 + 水印绘制 + 反转摄像头 + 拍之前显示时间+地点 + 图片上传到阿里云服务器

前言 uniapp，碰到新需求，反转摄像头，需要在打卡的时候对上传图片加上水印，拍照前就显示当前时间日期地点，拍摄后在呈现刚才拍摄的图加上水印，最好还需要将图片上传到阿里云。声明水印部分代码是借鉴的…...

编程日记 2025/7/14 19:06:33

南方电网场景中 Agent 的智慧赋能与创新实践（15/30）

一、南方电网的数字化变革浪潮在当今时代，能源领域正经历着深刻的变革，南方电网作为我国电力供应的重要支柱，面临着诸多挑战与机遇。随着经济的快速发展，用电需求持续攀升，电力负荷峰谷差日益增大，给电网的…...

编程日记 2025/7/14 13:05:02

rk3399增加新分区和计算规则

如果想要添加一个新的分区，例如添加名为"userdata"的分区，大小为，除了预留6G的system文件系统根目录分区（我这里是rootfs分区），剩下的空间全部给userdata。需要首先确定这个分区的起始地址。这个…...

编程日记 2025/7/19 4:18:37

风力涡轮机缺陷检测数据集，86.6％准确识别率，11921张图片，支持yolo，PASICAL VOC XML，COCO JSON格式的标注

风力涡轮机缺陷检测数据集，86.6％准确识别率，11921张图片，支持yolo，PASICAL VOC XML，COCO JSON格式的标注数据集下载 yolov11： https://download.csdn.net/download/pbymw8iwm/90206849 yolov…...

编程日记 2025/7/13 20:46:50

计算机网络-L2TP VPN基础实验配置

一、概述上次大概了解了L2TP的基本原理和使用场景，今天来模拟一个小实验，使用Ensp的网卡桥接到本地电脑试下L2TP拨号，今天主要使用标准的L2TP，其实在这个基础上可以加上IPSec进行加密，提高安全性。网络拓扑拓扑说明…...

编程日记 2025/7/14 8:11:51

QT集成IntelRealSense双目摄像头2，集成OpenGL

上一篇文章写了如何把IntelRealSense摄像头的SDK集成到QT项目，并成功采集数据，在没有用OpenCV的情况下完成色彩数据，以及深度数据的显示。具体地址：https://blog.csdn.net/qujia121qu/article/details/144734163 本次主要写如何…...

编程日记 2025/7/15 3:57:25

MySQL数据库——索引结构之B+树

本文先介绍数据结构中树的演化过程，之后介绍为什么MySQL数据库选择了B树作为索引结构。文章目录树的演化为什么其他树结构不行？为什么不使用二叉查找树（BST）？为什么不使用平衡二叉树（AVL树）&a…...

编程日记 2025/7/18 21:04:47

基于SpringBoot+Vue的旅游推荐系统

作者：计算机学姐开发技术：SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等，“文末源码”。专栏推荐：前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码精品专栏：…...

编程日记 2025/7/14 8:50:06

HTML——20 自定义属性

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>自定义属性</title></head><body><a href"https://ai.m.taobao.com" 自定义属性"属性值">淘宝网</a><a href"h…...

编程日记 2025/7/15 1:30:04

Java 简介、开发环境配置菜鸟教程编译运行 javac HelloWorld.java java HelloWorld Hello World public class HelloWorld {public static void main(String[] args) {System.out.println("Hello World");} }JAVA基础语法类、对象、方法、实例、变量对象&a…...

编程日记 2025/7/16 14:20:32

【Rust自学】8.2. Vector + Enum的应用

8.2.0. 本章内容第八章主要讲的是Rust中常见的集合。Rust中提供了很多集合类型的数据结构，这些集合可以包含很多值。但是第八章所讲的集合与数组和元组有所不同。第八章中的集合是存储在堆内存上而非栈内存上的，这也意味着这些集合的数据大小无需在编…...

编程日记 2025/7/19 7:12:39

机器算法之逻辑回归(Logistic Regression)详解

一、什么是逻辑回归？ 逻辑回归并不是传统意义上的回归分析，而是一种用于处理二分类问题的线性模型。它通过计算样本属于某一类别的概率来进行分类，尽管名字中有“回归”二字，但它实际上是一种分类算法。简单来说，逻辑…...

编程日记 2025/7/15 20:05:15

UE5材质节点VertexNormalWs/PixelNormalWS

VertexNormalWs顶点法线方向，此节点可以做物体上积雪、青苔等效果 PixelNormalWS像素法线方向...

编程日记 2025/6/30 22:39:59

NPM组件包 vant部分版本内嵌挖矿代码

Vant 是一个轻量、可定制的移动端组件库，于 2017 年开源。目前 Vant 官方提供了 Vue 2 版本、Vue 3 版本和微信小程序版本，并由社区团队维护 React 版本和支付宝小程序版本。 Vant 2 版本：https://vant-ui.github.io/vant/v2/#/zh-CN/home V…...

编程日记 2025/7/15 14:27:33

通过 Ansys Electronics Desktop 中的高级仿真优化 IC 设计

半导体行业继续通过日益复杂的集成电路 (IC) 设计突破技术界限。随着工艺节点缩小和电路密度达到前所未有的水平，电磁效应对设备性能和可靠性变得越来越重要。现代 IC 设计面临着来自复杂的布局相关耦合机制、信号完整性问题和功率分布问题的挑战，这些问…...

编程日记 2025/7/14 8:00:39

【Android】application@label 属性属性冲突报错

错误记录 What went wrong: Execution failed for task :app:processDebugMainManifest. > Manifest merger failed : Attribute applicationlabel value(string/app_name) from AndroidManifest.xml:8:9-41is also present at [:abslibrary] AndroidManifest.xml:25:9-47 v…...

编程日记 2025/7/16 12:43:40