LeetCode题练习与总结:有序链表转换二叉搜索树--109

news/2024/7/22 13:51:45/文章来源:https://blog.csdn.net/weixin_62860386/article/details/138329399

一、题目描述

给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为平衡二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

  • head 中的节点数在[0, 2 * 10^4] 范围内
  • -10^5 <= Node.val <= 10^5

二、解题思路

为了将一个升序链表转换为平衡的二叉搜索树(BST),我们可以利用链表的特性以及BST的性质。由于链表是升序的,我们可以通过快慢指针的方法找到链表的中间节点,这个中间节点就可以作为BST的根节点。然后,我们可以递归地将链表的前半部分转换为根节点的左子树,将链表的后半部分转换为根节点的右子树。

具体步骤如下:

  1. 使用快慢指针找到链表的中间节点,慢指针所在的位置即为中间位置,快指针用于确定慢指针的位置。

  2. 将慢指针指向的节点作为当前子树的根节点。

  3. 将链表从中间节点断开,分成左右两部分。

  4. 递归地将左半部分链表转换为根节点的左子树,将右半部分链表转换为根节点的右子树。

  5. 返回根节点,完成构建。

三、具体代码

class Solution {public TreeNode sortedListToBST(ListNode head) {if (head == null) {return null;}// Step 1: Find the middle of the listListNode mid = findMiddle(head);// Step 2: The middle node will be the root of the BSTTreeNode root = new TreeNode(mid.val);// Base case when there is only one element in the listif (head == mid) {return root;}// Step 3: Recursively build the left and right subtreesroot.left = sortedListToBST(head);root.right = sortedListToBST(mid.next);return root;}// Helper function to find the middle of the listprivate ListNode findMiddle(ListNode head) {ListNode prevPtr = null;ListNode slowPtr = head;ListNode fastPtr = head;// Iterate until fastPr doesn't reach the end of the listwhile (fastPtr != null && fastPtr.next != null) {prevPtr = slowPtr;slowPtr = slowPtr.next;fastPtr = fastPtr.next.next;}// If the slow pointer is not the first node, disconnect it from the listif (prevPtr != null) {prevPtr.next = null;}return slowPtr;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 查找中间节点:对于长度为 n 的链表,找到中间节点需要 O(n) 时间。
  • 递归构建左右子树:由于每次递归链表长度减半,所以递归的次数为 log(n)。
  • 每次递归中,除了递归调用本身,没有其他额外的操作。

综上所述,总的时间复杂度为 O(nlog(n))。

2. 空间复杂度
  • 递归栈空间:由于构建的是平衡二叉搜索树,递归的深度为 O(log(n)),因此递归栈的空间复杂度为 O(log(n))。
  • 辅助空间:除了递归栈之外,没有使用额外的空间。

综上所述,总的空间复杂度为 O(log(n))。

五、总结知识点

1. 链表操作

  • 遍历链表:使用while循环和指针遍历链表。
  • 快慢指针技巧:用于找到链表的中间节点,快指针每次移动两步,慢指针每次移动一步。

2. 递归

  • 递归是函数自己调用自己的过程,用于解决分而治之的问题,如这里的链表转换为二叉搜索树。

3. 二叉搜索树(BST)的性质

  • BST是一种特殊的二叉树,其中每个节点的左子树只包含小于当前节点的值,右子树只包含大于当前节点的值。

4. 平衡二叉树的构建

  • 通过选择链表的中间元素作为子树的根节点,可以保证构建出的二叉搜索树是平衡的。

5. 函数定义与调用

  • sortedListToBST 是主函数,负责启动递归过程。
  • findMiddle 是辅助函数,负责找到链表的中间节点并断开链表。

6. 指针和引用

  • 在Java中,虽然没有指针的概念,但是对象引用可以类比指针,用于操作对象。

7. 链表与树的转换

  • 将一个有序链表转换为平衡二叉搜索树,涉及到数据结构之间的转换。

8. 递归的终止条件

  • 当链表为空时,递归结束,返回null

9. 节点断开

  • 在找到中间节点后,需要将中间节点的前一个节点的next引用设置为null,从而断开链表。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1053207.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

区块链钱包如果丢失了私钥或助记词,资产还能恢复吗?

如果你丢失了区块链钱包的私钥或助记词&#xff08;通常是用于恢复钱包的短语或种子&#xff09;&#xff0c;那么你的资产在大多数情况下是无法恢复的。私钥是访问和控制你在区块链上资产的唯一凭证&#xff0c;而助记词&#xff08;如BIP39标准中的12、18、24个单词的短语&am…

MySQL中Undo-log是什么?有什么作用?

2.6.1. Undo-log撤销日志 Undo即撤销的意思&#xff0c;通常也称为回滚日志&#xff0c;用来给MySQL撤销SQL操作的。 当一条写入类型的SQL执行时&#xff0c;都会记录Undo-log日志&#xff0c;Undo-log并不存在单独的日志文件&#xff0c;InnoDB默认是将Undo-log存储在xx.ibd…

java项目——图书管理系统

文章目录 前言图书管理系统整体框架&#xff1a;book包user包Main包&#xff1a;iooperation包总结&#xff1a; 前言 针对这些天所学的javaSE的知识&#xff0c;用一个小项目来实践一下。 图书管理系统 整体框架&#xff1a; 采取面向对象的思想实现此项目&#xff0c;首先…

企业如何正确地利用LLM大模型?

大型语言模型 (LLM) 不值得信任。就是这样。 考虑到它们先进的 AI 能力以及当今强大的基础模型的普遍知识&#xff0c;这似乎是一件令人惊讶的事情。然而&#xff0c;问题的关键在于 LLM 无法解释其输出。你不能信任 LLM 的结果&#xff0c;不是因为它不准确&#xff0c;而是因…

超市进销存|基于SprinBoot+vue的超市进销存系统(源码+数据库+文档)

超市进销存系统 目录 基于SprinBootvue的超市进销存系统 一、前言 二、系统设计 三、系统功能设计 1 登录注册 2 管理员功能模块 3员工功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#x…

golang中的md5、sha256数据加密文件md5/sha256值计算步骤和运行内存图解

在go语言中对数据计算一个md5&#xff0c;或sha256和其他语言 如java, php中的使用方式稍有不同&#xff0c; 那就是要加密的数据必须通过流的形式写入到你创建的Hash对象中。 Hash数据加密步骤 1. 先使用对应的加密算法包中的New函数创建一个Hash对象&#xff0c;(这个也就是…

手搓单链表(无哨兵位)(C语言)

目录 SLT.h SLT.c SLTtest.c 测试示例 单链表优劣分析 SLT.h #pragma once#include <stdio.h> #include <assert.h> #include <stdlib.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next; }SLTNode;//打印…

Hololens 2 新建自定义按钮

官方链接地址 1、创建Cube 2、添加PressableButton脚本&#xff0c;并点击AddNearin… 3、把Cube拖入到MovingButtonVisuals变量中 4、点击NearInteractionTouchable组件&#xff08;这个组件是添加和上一个脚本绑定的&#xff0c;自动添加上来的&#xff09;上的Fix… 5、…

linux系统常用压缩和解压命令

文章目录 Ubuntu 系统中的文件压缩与解压指南一、常用的压缩和解压工具二、tar 工具三、gzip 工具四、bzip2 工具五、zip 和 unzip 工具六、7z 工具乱码批量解压脚本七、总结 Ubuntu 系统中的文件压缩与解压指南 在 Ubuntu 系统中&#xff0c;文件压缩与解压是日常操作中非常常…

《Effective Objective-C 2.0》读书笔记——对象、消息、运行期

目录 第二章&#xff1a;对象、消息、运行期第6条&#xff1a;理解“属性”这一概念第7条&#xff1a;在对象内部尽量直接访问实例变量第8条&#xff1a;理解“对象等同性”这一概念第9条&#xff1a;以“类族模式”隐藏实现细节第10条&#xff1a;在既有类中使用关联对象存放自…

RSC英国皇家化学学会文献查找下载

英国皇家化学学会(Royal Society of Chemistry&#xff0c;简称RSC)是以促进全球化学领域研究发展与传播为宗旨的国际权威学术机构&#xff0c;是化学信息的一个重要宣传机关和出版商。RSC出版的期刊是化学领域的核心期刊&#xff0c;大部分被SCI和MEDLINE收录&#xff0c;如An…

堆排序和Topk问题

堆排序 堆排序即利用堆的思想来进行排序&#xff0c; 总共分为两个步骤&#xff1a; 1. 建堆 升序&#xff1a;建大堆&#xff1b; 降序&#xff1a;建小堆 2 .利用堆删除思想来进行排序 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整&#xff0c;因此掌握了…

260 基于matlab的工业乙醇发酵GUI仿真

基于matlab的工业乙醇发酵GUI仿真。首先对经典的流加半经验半理论模型进行动态和稳态仿真&#xff0c;考虑实际情况密&#xff0c;逐步将温度&#xff0c;气体排放等因素考虑到模型中去&#xff0c;进行综合性仿真。结合GUI技术&#xff0c;以动力学模型为核心&#xff0c;制作…

【组合数学 放球问题 虚拟点 小于等于转小于】1621. 大小为 K 的不重叠线段的数目

本文涉及知识点 放球问题 组合数学汇总 本题难道分&#xff1a;2198 LeetCode1621. 大小为 K 的不重叠线段的数目 给你一维空间的 n 个点&#xff0c;其中第 i 个点&#xff08;编号从 0 到 n-1&#xff09;位于 x i 处&#xff0c;请你找到 恰好 k 个不重叠 线段且每个线段…

VUE3+TS+elementplus+Django+MySQL实现从数据库读取数据,显示在前端界面上

一、前言 前面通过VUE3和elementplus创建了一个table&#xff0c;VUE3TSelementplus创建table&#xff0c;纯前端的table&#xff0c;以及使用VUE3TSelementplus创建一个增加按钮&#xff0c;使用前端的静态数据&#xff0c;显示在表格中。今天通过从后端获取数据来显示在表格…

大数据开发面试题【Kafka篇】

83、介绍下Kafka&#xff0c;Kafka的作用?Kafka的组件?适用场景? kafka是一个高吞吐量、可扩展的分布式消息传递系统&#xff0c;在处理实时流式数据&#xff0c;并能够保证持久性和容错性 可用于数据管道、流分析和数据继承和关键任务应用&#xff08;发布/订阅模式&#…

【Python】 Django 框架如何支持百万级日访问量

基本原理 Django 是一个高级的 Python Web 框架&#xff0c;它鼓励快速开发和干净、实用的设计。Django 遵循 MVC&#xff08;模型-视图-控制器&#xff09;设计模式&#xff0c;允许开发者通过编写更少的代码来构建高质量的 Web 应用程序。Django 自带了许多内置功能&#xf…

学习笔记——STM32F103V3版本——HC-05模块控制数码管

一.硬件 1.HC-05模块 2.数码管 3.连接硬件 二.在keil5中的代码 main.c代码&#xff1a; #include "stm32f10x.h" #include "buletooth.h" #include "led.h" #include "sys.h" #include "usart.h" #include "delay.…

目标检测数据集 - 工地工人安全设备佩戴检测数据集下载「包含VOC、COCO、YOLO三种格式」

数据集介绍&#xff1a;工地工人安全设备佩戴检测数据集&#xff0c;真实场景数据生成增强后高质量图片数据&#xff0c;涉及场景丰富&#xff0c;比如楼宇建筑工地工人作业数据、道路建筑工地工人作业数据、室内工地工人作业数据、露天挖掘场景工人作业数据、工地工人自拍摆拍…

SpringBoot+layuimini实现角色权限菜单增删改查(layui扩展组件 dtree)

角色菜单 相关组件方法效果图MySQL代码实现资源菜单树组件实现权限树方法js这里我先主要实现权限树的整体实现方法&#xff0c;如果是直接查看使用的话可以只看这里&#xff01; 后端代码Controlle层代码Service代码及实现类代码Service代码ServiceImpl代码 resourceMapper 代码…