LC109. 有序链表转换平衡二叉搜索树
LC109. 有序链表转换平衡二叉搜索树
- 题目要求
- (一)快慢指针
- 1. 理解问题
- 2. 解决思路
- 3. 具体步骤
- 4. 代码实现
- 5. 复杂度分析
- 6. 示例解释
- 7. 总结
LC109. 有序链表转换平衡二叉搜索树
题目要求

(一)快慢指针
要将一个按升序排列的单链表转换为平衡的二叉搜索树(BST),可以采用以下步骤:
1. 理解问题
- 单链表:链表中的节点按升序排列。
- 平衡二叉搜索树:树的左右子树高度差不超过1,且左子树的值小于根节点,右子树的值大于根节点。
2. 解决思路
由于链表是升序排列的,我们可以将其视为二叉搜索树的中序遍历结果。为了构建平衡的BST,我们需要找到链表的中间节点作为根节点,然后递归地构建左子树和右子树。
3. 具体步骤
-
找到链表的中间节点:
- 使用快慢指针法找到链表的中间节点。快指针每次走两步,慢指针每次走一步,当快指针到达链表末尾时,慢指针指向的就是中间节点。
-
递归构建BST:
- 将中间节点作为根节点。
- 递归地构建左子树(链表的前半部分)和右子树(链表的后半部分)。
-
处理边界条件:
- 如果链表为空,返回
null。 - 如果链表只有一个节点,直接返回该节点作为树的根节点。
- 如果链表为空,返回
4. 代码实现
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef sortedListToBST(head):if not head:return None# 找到链表的中间节点def findMiddle(head):slow = headfast = headprev = Nonewhile fast and fast.next:prev = slowslow = slow.nextfast = fast.next.next# 断开链表if prev:prev.next = Nonereturn slow# 递归构建BSTdef buildBST(head):if not head:return Nonemid = findMiddle(head)root = TreeNode(mid.val)# 如果只有一个节点,直接返回if head == mid:return root# 递归构建左子树和右子树root.left = buildBST(head)root.right = buildBST(mid.next)return rootreturn buildBST(head)
5. 复杂度分析
- 时间复杂度:O(N log N),其中 N 是链表的长度。每次递归都需要找到中间节点,时间复杂度为 O(N),递归深度为 O(log N)。
- 空间复杂度:O(log N),递归栈的深度为 O(log N)。
6. 示例解释
对于输入 head = [-10,-3,0,5,9]:
- 中间节点是
0,作为根节点。 - 左子树由
[-10, -3]构建,右子树由[5, 9]构建。 - 最终得到的平衡BST为
[0,-3,9,-10,null,5]。
7. 总结
通过找到链表的中间节点并将其作为根节点,然后递归地构建左子树和右子树,我们可以将一个升序链表转换为一个平衡的二叉搜索树。这种方法既保证了树的平衡性,又充分利用了链表的升序特性。
相关文章:
LC109. 有序链表转换平衡二叉搜索树
LC109. 有序链表转换平衡二叉搜索树 题目要求(一)快慢指针1. 理解问题2. 解决思路3. 具体步骤4. 代码实现5. 复杂度分析6. 示例解释7. 总结 LC109. 有序链表转换平衡二叉搜索树 题目要求 (一)快慢指针 要将一个按升序排列的单链表转换为平衡的二叉搜索树(BST&…...
Hutool一个类型转换工具类 `Convert`,
Hutool 是一个非常实用的Java工具库,旨在简化Java开发中的常见任务。它包含了一个类型转换工具类 Convert,可以帮助开发者轻松地进行各种类型之间的转换。以下是一些使用 Convert 类进行类型转换的例子: 基本类型转换 假设你需要将一个字符…...
基于eRDMA实测DeepSeek开源的3FS
DeepSeek昨天开源了3FS分布式文件系统, 通过180个存储节点提供了 6.6TiB/s的存储性能, 全面支持大模型的训练和推理的KVCache转存以及向量数据库等能力, 每个客户端节点支持40GB/s峰值吞吐用于KVCache查找. 发布后, 我们在阿里云ECS上进行了快速的复现, 并进行了性能测试, ECS…...
【Linux篇】第一个系统程序 - 进度条
文章目录 1.回车与换行2.行缓冲区3.倒计时程序4.进度条 1.回车与换行 回车的概念: 回到当前行的最开始 \r换行的概念: 换到当前行的下一行\n 2.行缓冲区 当我们运行下面这段程序时,我们会发现屏幕上首先会打印出hello world!,再过两秒后程序结束。 当我们把\n去掉…...
VLM-E2E:通过多模态驾驶员注意融合增强端到端自动驾驶
25年2月来自香港科大广州分校、理想汽车和厦门大学的论文“VLM-E2E: Enhancing End-to-End Autonomous Driving with Multimodal Driver Attention Fusion”。 人类驾驶员能够利用丰富的注意语义,熟练地应对复杂场景,但当前的自动驾驶系统难以复制这种能…...
如何将飞书多维表格与DeepSeek R1结合使用:效率提升的完美搭档
将飞书的多维表格与DeepSeek R1结合使用,就像为你的数据管理和分析之旅装上一台涡轮增压器。两者的合作,不仅仅在速度上让人耳目一新,更是将智能化分析带入了日常的工作场景。以下是它们如何相辅相成并改变我们工作方式的一些分享。 --- 在…...
Kali CentOs 7代理
工具v2↓ kali_IP段v2端口例子<1> kali_IP段v2端口例子<2> CentOs 7 //编辑配置文件 vi /etc/profile//在该配置文件的最后添加代理配置 export http_proxyhttp://ip:port //代理服务器ip地址和端口号 export https_proxyhttp://ip:port //代理服务器ip地址和…...
Zookeeper 的核心引擎:深入解析 ZAB 协议
#作者:张桐瑞 文章目录 前言ZAB 协议算法崩溃恢复选票结构选票筛选消息广播 前言 ZooKeeper 最核心的作用就是保证分布式系统的数据一致性,而无论是处理来自客户端的会话请求时,还是集群 Leader 节点发生重新选举时,都会产生数据…...
L3-001 凑零钱
L3-001 凑零钱 - 团体程序设计天梯赛-练习集 n, m map(int, input().split()) a list(map(int, input().split())) a.sort() f [[] for _ in range(m 1)] f[0] [0] for i in a:for j in range(m, i - 1, -1):if f[j - i]:if not f[j] or f[j] > f[j - i] [i]:f[j] f…...
命名管道(用命名管道模拟server和client之间的通信)
目录 命名管道创建命名管道使用命令行创建命名管道(FIFO)在程序中创建 命名管道的打开规则用命名管道实现server和client通信 命名管道 bash进程并不会给我们写的两个不同的程序创建通信的管道,即使这两个进程看起来好像都是bash的子进程&am…...
【AI深度学习基础】Pandas完全指南入门篇:数据处理的瑞士军刀 (含完整代码)
📚 Pandas 系列文章导航 入门篇 🌱进阶篇 🚀终极篇 🌌 📌 一、引言 在大数据与 AI 驱动的时代,数据预处理和分析是深度学习与机器学习的基石。Pandas 作为 Python 生态中最强大的数据处理库,以…...
关于opencv中solvepnp中UPNP与DLS与EPNP的参数
The methods SOLVEPNP_DLS and SOLVEPNP_UPNP cannot be used as the current implementations are unstable and sometimes give completely wrong results. If you pass one of these two flags, SOLVEPNP_EPNP method will be used instead.、 由于当前的实现不稳定&#x…...
金融项目实战
测试流程 测试流程 功能测试流程 功能测试流程 需求评审制定测试计划编写测试用例和评审用例执行缺陷管理测试报告 接口测试流程 接口测试流程 需求评审制定测试计划分析api文档编写测试用例搭建测试环境编写脚本执行脚本缺陷管理测试报告 测试步骤 测试步骤 需求评审 需求评…...
大模型小白入门
【课前篇】大模型从0到1指南 【基础篇】大模型的演变与概念 大模型的演变 人工智能:人工智能是一个广泛涉及计算机科学、数据分析、统计学、机器工程、语言学、神 经科学、哲学和心理学等多个学科的领域。 机器学习:机器学习可以分为监督学习&…...
从零到一:快速上手 Poetry——Python 项目管理的利器
在 Python 项目开发中,包管理、依赖管理和虚拟环境的创建一直是开发者们经常面对的难题。传统上,开发者通常会使用 pip、virtualenv 或者 conda 来处理这些问题。然而,随着 Python 项目复杂度的增加,传统工具往往显得力不从心&…...
【量化科普】Beta,贝塔系数
【量化科普】Beta,贝塔系数 🚀量化软件开通 🚀量化实战教程 在量化投资领域,Beta(贝塔系数)是一个衡量投资组合或股票相对于整个市场波动性的指标。它反映了资产收益与市场收益之间的相关性,…...
C++----异常
一、C 语言传统的错误处理方式 在 C 语言中,处理错误主要有两种传统方式,每种方式都有其特点和局限性。 1. 终止程序 原理:使用类似assert这样的断言机制,当程序运行到某个条件不满足时,直接终止程序的执行。示例代…...
合理规划时间,从容应对水利水电安全员考试
合理规划时间,从容应对水利水电安全员考试 在忙碌的工作与生活节奏中备考水利水电安全员考试,合理规划时间是实现高效备考的核心。科学的时间管理能让你充分利用每一分每一秒,稳步迈向考试成功。 制定详细的学习计划是第一步。依据考试时间…...
(解决) Windows 11使用SetSuspendState睡眠命令但是进入的是休眠
Windows 11 24H2 goes into hibernation mode instead of sleep mode. How can I create a sleep mode shortcut file? 25年3月4号 Win11 23H2 起因 使用网上说的睡眠命令创建bat双击后,电脑风扇会运行一段时间后再停止(应该是在保存进程到硬盘&#…...
Spring Boot 接口 JSON 序列化优化:忽略 Null 值的九种解决方案详解
一、针对特定接口null的处理: 方法一:使用 JsonInclude 注解 1.1 类级别:在接口返回的 DTO 类或字段 上添加 JsonInclude 注解,强制忽略 null 值: 类级别:所有字段为 null 时不返回 JsonInclude(Js…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
Linux基础开发工具——vim工具
文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...
麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
