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

力扣每日一题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(log⁡n),这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(log⁡n),即为递归过程中栈的最大深度,也就是需要的空间。

相关文章:

力扣每日一题109:有序链表转换二叉搜索树

题目 中等 给定一个单链表的头节点 head &#xff0c;其中的元素 按升序排序 &#xff0c;将其转换为 平衡 二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0&#xff0c;-3,9&#xff0c;-10,null,5]&#xff0c;它…...

企业计算机服务器中了locked勒索病毒怎么处理,locked勒索病毒解密建议

随着互联网技术在企业当中的应用&#xff0c;越来越多的企业利用网络开展各项工作业务&#xff0c;网络为企业提供了极大便利&#xff0c;也大大加快了企业发展步伐&#xff0c;提高了企业生产办公效率。但网络技术的发展也为企业的数据安全带来严重威胁。近期&#xff0c;云天…...

开源推荐榜【MalusAdmin基于 Vue3/TypeScript/NaiveUI 和 NET7 Sqlsugar 开发的后台管理框架】

简介 Malus是海棠的意思&#xff0c;顾名思义&#xff0c;海棠后台管理系统&#xff0c;读音与【马卢斯】相近&#xff0c;也可称作为马卢斯后台管理系统。 基于NET Core | NET7/8 & Sqlsugar | Vue3 | vite4 | TypeScript | NaiveUI 开发的前后端分离式权限管理系统,采用…...

批量抓取某电影网站的下载链接

思路&#xff1a; 进入电影天堂首页&#xff0c;提取到主页面中的每一个电影的背后的那个urL地址 a. 拿到“2024必看热片”那一块的HTML代码 b. 从刚才拿到的HTML代码中提取到href的值访问子页面&#xff0c;提取到电影的名称以及下载地址 a. 拿到子页面的页面源代码 b. 数据提…...

2024-05-06 问AI: 介绍一下深度学习中的LSTM网络

文心一言 当谈到深度学习中的LSTM&#xff08;Long Short-Term Memory&#xff09;网络时&#xff0c;它是一种特殊的循环神经网络&#xff08;RNN&#xff09;架构&#xff0c;旨在解决传统RNN在处理长序列时遇到的梯度消失和梯度爆炸问题。LSTM网络因其能够捕捉序列数据中的…...

二、Redis五种常用数据类型-String

1、用途 简单的K-V缓存计数器分布式锁session共享分布式ID生成(自增) 2、底层实现结构 Redis底层是c语言实现的&#xff0c;但是并没有使用c的string来表示字符串&#xff0c;而是使用自己的简单动态字符串的抽象类型(simple dynamic string,SDS)。 SDS结构&#xff1a; st…...

echarts柱状图实现左右横向对比

实现效果如上图 其实是两组数据&#xff0c;其中一组数据改为负数&#xff0c;然后 在展示的时候&#xff0c;在将负数取反 第一处修改坐标轴 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&#xff0c;注解扫描 <context:component-scan base-package"com.zhou.spring.aop.xml"></context:component-scan><aop:config> <!-- 设置一个公共的切入点表达式--><aop:pointcut id&q…...

【挑战30天首通《谷粒商城》】-【第一天】02、简介-项目整体效果展示

文章目录 课程介绍 ( 本章了解即可&#xff0c;可以略过)一、 分布式基础 (全栈开发篇) (初中级)二、 分布式高级 (微服务架构篇) ( 高级)三、高可用集群 (架构师提升篇)( 架构 ) one more thing 课程介绍 ( 本章了解即可&#xff0c;可以略过) 1.分布式基础(全栈开发篇)2.分布…...

Kafka 生产者应用解析

目录 1、生产者消息发送流程 1.1、发送原理 2、异步发送 API 2.1、普通异步发送 2.2、带回调函数的异步发送 3、同步发送 API 4、生产者分区 4.1、分区的优势 4.2、生产者发送消息的分区策略 示例1&#xff1a;将数据发往指定 partition 示例2&#xff1a;有 key 的…...

GEE错误——image.reduceRegion is not a function

简介 image.reduceRegion is not a function 这里的主要问题是我们进行地统计分析的时候&#xff0c;我们的作用对象必须是单景影像&#xff0c;而不是影像集合 错误"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 &#xff0c;不是在地址栏输入(切记)&#xff0c;就直接敲键盘就行了 因为Chrome不信任这些自签名ssl证书&#xff0c;为了安全起见&#xff0c;直接禁止访问了&#xff0c;thisisunsafe 这个命令&#xff0c;说明你…...

牛客面试前端1

HTML语义化 是什么 前端语义化是指在构建网页时多使用html语义化标签布局&#xff0c;多使用带有语义的标签如header&#xff0c;aside&#xff0c;footer等标签为什么 结构清晰利于开发者开发与维护 有利于seo搜索引擎优化 有利于在网络卡顿时&#xff0c;正常显示页面结构&a…...

Linux的软件包管理器-yum

文章目录 软件包的概念yum源的配置的原因yum的使用查看软件包安装软件卸载软件 软件包的概念 软件包(SoftWare Package)是指具有特定的功能&#xff0c;用来完成特定任务的一个程序或一组程序。可分为应用软件包和系统软件包两大类 在Linux系统中&#xff0c;下载安装软件的方式…...

选择排序(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融屏视频混流会议直播方案分析

随着万物互联&#xff0c;视频会议直播互动深入业务各方面&#xff0c;主流SFU并不适合管理&#xff0c;很多业务需要各种监控终端&#xff0c;互动SIP硬件设备&#xff0c;Web在线业务平台能相互融合&#xff0c;互联互通&#xff0c; 视频混流直播&#xff0c;录存直播推广&a…...

Unreal 编辑器工具 批量重命名资源

右键 - Editor Utilities - Editor Utility Blueprint&#xff0c;基类选择 Asset Action Utility 在类默认值内&#xff0c;可以添加筛选器&#xff0c;筛选指定的类型 然后新建一个函数&#xff0c;加上4个输入&#xff1a;ReplaceFrom&#xff0c;ReplaceTo&#xff0c;Add…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...