力扣每日一题109:有序链表转换二叉搜索树
题目
中等
给定一个单链表的头节点 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 * 104]范围内-105 <= Node.val <= 105
面试中遇到过这道题?
1/5
是
否
通过次数
161.6K
提交次数
211K
通过率
76.6%
思路
和有序数组转换为二叉搜索树的的思路一样,都是以中间值为根,然后递归建立左右子树。区别就是:如果是数组的话,直接用下标就能找到中间元素,如果是有序链表的话,用快慢指针寻找中间元素、或是知道链表长度情况下,根据遍历次数寻找中间元素。
链表和树的结点结构
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*//*
方法一:根据遍历次数寻找中间元素。
class Solution {
public:TreeNode *build(ListNode *head,int lo,int hi){if(lo>hi) return NULL;//找中间位置int mid=(lo+hi)/2;ListNode *middle=head;for(int i=0;i<mid-lo;i++){middle=middle->next;}//建根,递归建立左右子树TreeNode *root=new TreeNode(middle->val);root->left=build(head,lo,mid-1);root->right=build(middle->next,mid+1,hi);return root;}TreeNode* sortedListToBST(ListNode* head) {int n=0;ListNode *p=head;while(p){n++;p=p->next;}return build(head,0,n-1);}
};
方法二:快慢指针寻找中间元素
使用快慢指针寻找中间元素是链表题目的基操。原理就是,设置一个快指针fast和一个慢指针slow,快指针的速度是慢指针的两倍,当快指针走到最后的时候,慢指针就到了中间位置。
class Solution {
public:ListNode* getMedian(ListNode* left, ListNode* right) {ListNode* fast = left;ListNode* slow = left;while (fast != right && fast->next != right) {fast = fast->next;fast = fast->next;slow = slow->next;}return slow;}TreeNode* buildTree(ListNode* left, ListNode* right) {if (left == right) {return nullptr;}ListNode* mid = getMedian(left, right);TreeNode* root = new TreeNode(mid->val);root->left = buildTree(left, mid);root->right = buildTree(mid->next, right);return root;}TreeNode* sortedListToBST(ListNode* head) {return buildTree(head, nullptr);}
};
方法三:分治+中序遍历优化
上面的两种方法都是先找到中间节点,再递归建立左右子树,属于先序遍历。这样,每次寻找中间节点时,就要logn的时间复杂度,总的时间复杂度变成了O(nlogn)。
如果我们可以用中序遍历,先建立左子树,左子树建完再建根,然后再建右子树,那么就省去了查找中间节点的时间,时间复杂度就变成了O(n)。
也就是说,我们没有必要“先”找到中间节点:我们可以先构建了左子树,建立结束后,指针自然指向中间结点。那么如何构建左子树呢?其实我们只需要确定子树的大小就可以。所以先用O(n)的时间计算链表长度,之后用中序遍历。当然,指针需要是“引用”,这样才能改变指针的指向,实现建好左子树后,指针自然指向中间结点。
下面是官方题解:
class Solution {
public:int getLength(ListNode* head) {int ret = 0;for (; head != nullptr; ++ret, head = head->next);return ret;}TreeNode* buildTree(ListNode*& head, int left, int right) {if(left>right) return NULL;int mid=(left+right)/2;TreeNode *root=new TreeNode();root->left=buildTree(head,left,mid-1);root->val=head->val;head=head->next;root->right=buildTree(head,mid+1,right);return root;}TreeNode* sortedListToBST(ListNode* head) {int length = getLength(head);return buildTree(head, 0, length - 1);}
};
时间复杂度:O(n),其中 n 是链表的长度。
设长度为 n 的链表构造二叉搜索树的时间为 T(n),递推式为 T(n)=2⋅T(n/2)+O(1),根据主定理,T(n)=O(n)。
空间复杂度:O(logn),这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(logn),即为递归过程中栈的最大深度,也就是需要的空间。
相关文章:
力扣每日一题109:有序链表转换二叉搜索树
题目 中等 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为 平衡 二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它…...
企业计算机服务器中了locked勒索病毒怎么处理,locked勒索病毒解密建议
随着互联网技术在企业当中的应用,越来越多的企业利用网络开展各项工作业务,网络为企业提供了极大便利,也大大加快了企业发展步伐,提高了企业生产办公效率。但网络技术的发展也为企业的数据安全带来严重威胁。近期,云天…...
开源推荐榜【MalusAdmin基于 Vue3/TypeScript/NaiveUI 和 NET7 Sqlsugar 开发的后台管理框架】
简介 Malus是海棠的意思,顾名思义,海棠后台管理系统,读音与【马卢斯】相近,也可称作为马卢斯后台管理系统。 基于NET Core | NET7/8 & Sqlsugar | Vue3 | vite4 | TypeScript | NaiveUI 开发的前后端分离式权限管理系统,采用…...
批量抓取某电影网站的下载链接
思路: 进入电影天堂首页,提取到主页面中的每一个电影的背后的那个urL地址 a. 拿到“2024必看热片”那一块的HTML代码 b. 从刚才拿到的HTML代码中提取到href的值访问子页面,提取到电影的名称以及下载地址 a. 拿到子页面的页面源代码 b. 数据提…...
2024-05-06 问AI: 介绍一下深度学习中的LSTM网络
文心一言 当谈到深度学习中的LSTM(Long Short-Term Memory)网络时,它是一种特殊的循环神经网络(RNN)架构,旨在解决传统RNN在处理长序列时遇到的梯度消失和梯度爆炸问题。LSTM网络因其能够捕捉序列数据中的…...
二、Redis五种常用数据类型-String
1、用途 简单的K-V缓存计数器分布式锁session共享分布式ID生成(自增) 2、底层实现结构 Redis底层是c语言实现的,但是并没有使用c的string来表示字符串,而是使用自己的简单动态字符串的抽象类型(simple dynamic string,SDS)。 SDS结构: st…...
echarts柱状图实现左右横向对比
实现效果如上图 其实是两组数据,其中一组数据改为负数,然后 在展示的时候,在将负数取反 第一处修改坐标轴 xAxis: [{type: value,axisLabel: {formatter: function (value) {if (value < 0) {return -value;}else{return value;}}}}], 第…...
脸爱云一脸通智慧管理平台 SystemMng 管理用户信息泄露漏洞(XVE-2024-9382)
0x01 产品简介 脸爱云一脸通智慧管理平台是一套功能强大,运行稳定,操作简单方便,用户界面美观,轻松统计数据的一脸通系统。无需安装,只需在后台配置即可在浏览器登录。 功能包括:系统管理中心、人员信息管理中心、设备管理中心、消费管理子系统、订餐管理子系统、水控管…...
spring笔记2
一、基于xml的AOP实现 基于注解管理Bean,注解扫描 <context:component-scan base-package"com.zhou.spring.aop.xml"></context:component-scan><aop:config> <!-- 设置一个公共的切入点表达式--><aop:pointcut id&q…...
【挑战30天首通《谷粒商城》】-【第一天】02、简介-项目整体效果展示
文章目录 课程介绍 ( 本章了解即可,可以略过)一、 分布式基础 (全栈开发篇) (初中级)二、 分布式高级 (微服务架构篇) ( 高级)三、高可用集群 (架构师提升篇)( 架构 ) one more thing 课程介绍 ( 本章了解即可,可以略过) 1.分布式基础(全栈开发篇)2.分布…...
Kafka 生产者应用解析
目录 1、生产者消息发送流程 1.1、发送原理 2、异步发送 API 2.1、普通异步发送 2.2、带回调函数的异步发送 3、同步发送 API 4、生产者分区 4.1、分区的优势 4.2、生产者发送消息的分区策略 示例1:将数据发往指定 partition 示例2:有 key 的…...
GEE错误——image.reduceRegion is not a function
简介 image.reduceRegion is not a function 这里的主要问题是我们进行地统计分析的时候,我们的作用对象必须是单景影像,而不是影像集合 错误"image.reduceRegion is not a function" 表示你正在尝试使用reduceRegion()函数来处理图像数据&…...
rk356x 关于yocto编译linux及bitbake实用方法
Yocto 完整编译 source oe-init-build-envbitbake core-image-minimalYocto 查询包名 bitbake -s | grep XXX // 获取rockchip相关包 :~/rk3568/yocto$ bitbake -s | grep rockchip android-tools-conf-rockchip :1.0-r0 gstreamer1.0-rockchip …...
Chrome您的连接不是私密连接 |输入“thisisunsafe”命令绕过警告or添加启动参数
一、输入 thisisunsafe 在当前页面用键盘输入 thisisunsafe ,不是在地址栏输入(切记),就直接敲键盘就行了 因为Chrome不信任这些自签名ssl证书,为了安全起见,直接禁止访问了,thisisunsafe 这个命令,说明你…...
牛客面试前端1
HTML语义化 是什么 前端语义化是指在构建网页时多使用html语义化标签布局,多使用带有语义的标签如header,aside,footer等标签为什么 结构清晰利于开发者开发与维护 有利于seo搜索引擎优化 有利于在网络卡顿时,正常显示页面结构&a…...
Linux的软件包管理器-yum
文章目录 软件包的概念yum源的配置的原因yum的使用查看软件包安装软件卸载软件 软件包的概念 软件包(SoftWare Package)是指具有特定的功能,用来完成特定任务的一个程序或一组程序。可分为应用软件包和系统软件包两大类 在Linux系统中,下载安装软件的方式…...
选择排序(Selection Sort)
选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下: 遍历数组:从待排序的数列中,找到当前未排序部分(即整个数组或已排序部分之后的部分)中的最小(或最大,取决于排序方式)元素。 交换位置:将找到的最小元素与未排序部分的第一个元素交换位置,这…...
网络面试题目
1、BGP报文有哪些? 有5种报文,Open、 Update、 Notification、 Keepalive和 Route-refresh等5种报文类型。 2、Vxlan了解多少? VLAN作为传统的网络隔离技术,VXLAN完美地弥补了VLAN的上述不足。 VXLAN(Virtual eXtensible Local Area Network,虚拟扩展局域网),(VXL…...
Web,Sip,Rtsp,Rtmp,WebRtc,专业MCU融屏视频混流会议直播方案分析
随着万物互联,视频会议直播互动深入业务各方面,主流SFU并不适合管理,很多业务需要各种监控终端,互动SIP硬件设备,Web在线业务平台能相互融合,互联互通, 视频混流直播,录存直播推广&a…...
Unreal 编辑器工具 批量重命名资源
右键 - Editor Utilities - Editor Utility Blueprint,基类选择 Asset Action Utility 在类默认值内,可以添加筛选器,筛选指定的类型 然后新建一个函数,加上4个输入:ReplaceFrom,ReplaceTo,Add…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
