Leetcode 109.有序链表转换二叉搜索树(Medium)
给定一个单链表的头节点 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 <= 10
思路:先获取到链表的长度,然后去递归构造树即可,每次构造的树节点永远是链表或子链表的中心,但是由于是单向链表,所以每次获取链表中的节点的时候就会导致每次都从头开始,可以用循环链表改善,如果要构造的节点的坐标大于length/2的时候就next length -index次,然后递归构造,设置临界条件即可,若length为0就是无节点,如果length为1就是叶子节点。然后上代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {ListNode temp;public TreeNode sortedListToBST(ListNode head) {temp = head;// 思路就是取链表的中心节点,作为总树或子树的根节点,然后循环、递归int length = getListLength(head);return buildTree(0, length);}public TreeNode buildTree(int start ,int length) {int i = 0;ListNode t = temp;while (i < start + length/2) {t = t.next;i++;}// 如果是0,直接为nullif (length == 0) return null;// 如果length为1的时候,直接返回,因为它已经是树叶节点了if (length == 1) return new TreeNode(t.val, null, null);// 遍历到中心节点,就构造节点return new TreeNode(t.val, buildTree(start, length/2), buildTree(start + length/2 +1, length-1-length/2));}// 获取节点总节点数public int getListLength(ListNode head) {int length = 0;while(head != null) {length++;head = head.next;}return length;}}
快慢指针也是解决中间值问题的一个快速的解决办法,思路相同,只是取中间值的方法不同。
class Solution {public TreeNode sortedListToBST(ListNode head) {return buildTree(head, null);}public TreeNode buildTree(ListNode left, ListNode right) {if (left == right) {return null;}ListNode mid = getMedian(left, right);TreeNode root = new TreeNode(mid.val);root.left = buildTree(left, mid);root.right = buildTree(mid.next, right);return root;}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;}
}
相关文章:
Leetcode 109.有序链表转换二叉搜索树(Medium)
给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为 平衡 二叉搜索树。 示例 1: 输入: head [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度…...
[数据集][目标检测]河道垃圾检测数据集VOC+YOLO格式2274张8类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):2274 标注数量(xml文件个数):2274 标注数量(txt文件个数):2274 标注…...
python vtk 绘制圆柱体和包围盒
基本的代码如下, import vtkcylinder vtk.vtkCylinderSource() cylinder.SetRadius(3.0) cylinder.SetHeight(10.0) cylinder.SetResolution(50)boundsFilter vtk.vtkOutlineFilter() boundsFilter.SetInputConnection(cylinder.GetOutputPort())mapper vtk.vtk…...
Fisco Bcos 2.11.0通过网络和本地二进制文件搭建单机节点联盟链网络(搭建你的第一个区块链网络)
Fisco Bcos 2.11.0通过网络和本地二进制文件搭建单机节点联盟链网络(搭建你的第一个区块链网络) 文章目录 Fisco Bcos 2.11.0通过网络和本地二进制文件搭建单机节点联盟链网络(搭建你的第一个区块链网络)前言一、Ubuntu依赖安装二、创建操作目录, 下载build_chain.sh脚本2.1 先…...
【Canvas与表盘】绘制黄蓝两色简约表盘
【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>黄蓝卡通手表</title><style type"text/css">…...
大数据-128 - Flink 并行度设置 细节详解 全局、作业、算子、Slot
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...
图新地球-将地图上大量的地标点批量输出坐标到csv文件【kml转excel】
0.序 有很多用户需要在卫星影像、或者无人机航测影像、倾斜模型上去标记一些地物的位置(如电线杆塔、重点单位、下水盖等) 标记的位置最终又需要提交坐标文本文件给上级单位或者其他部门使用,甚至需要转为平面直角坐标。 本文的重点是通过of…...
Git提交有乱码
服务器提交记录如图 可知application.properties中文注释拉黄线 ,提示Unsupported characters for the charset ISO-8859-1 打开settings - Editor - File Encodings 因为我们项目的其他文件都是UTF-8,所以,我们将默认值都改成UTF-8 然后…...
leetcode hot100_part4_子串
2024/4/20—4/21 560.和为K的子数组 前缀和哈希表,做二叉树的时候也有这个套路。注意细节,遍历到当前前缀和的时候是先找结果个数还是先加入哈希?应该先找结果个数,不然的话,当前位置也算上了(因为是前缀和…...
Spring Cloud之三 网关 Gateway
1:Intellij 新建项目 spring-cloud-gateway 2:pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLoca…...
Linux 进程1
进程 在linux系统中,触发任何一个事件时系统会将其定义为一个进程(一个程序开始执行),系统会给这个进程分配一个进程ID统称为PID。 程序:通常是二进制文件,放置于存储媒介如硬盘中。 进程:当存…...
LeetCode: 2552. 统计上升四元组 动态规划 时间复杂度O(n*n)
2552. 统计上升四元组 today 2552. 统计上升四元组 题目描述 给你一个长度为n下标从 0 开始的整数数组 nums ,它包含1到n的所有数字,请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足以下条件,我们称它是上升的:…...
Unity 编辑器设置中文
在 Unity 编辑器中,你可以按照以下步骤将语言设置为中文: 步骤: 1. 打开 Unity 编辑器。 2. 在顶部菜单栏,依次点击 Edit > Preferences(在 macOS 上是 Unity > Preferences)。 3. 在弹出的 Preferen…...
springboot-创建连接池
操作数据库 代码开发步骤: pom.xml文件配置依赖properties文件配置连接数据库信息(连接池用的是HikariDataSource)数据库连接池开发 configurationproperties和value注解从properties文件中取值bean方法开发 service层代码操作数据库 步骤&am…...
matlab绘制不同区域不同色彩的图,并显示数据(代码)
绘图结果如下: 代码如下: A为绘图的数据,每个数据对应着上图中的一个区域,数据大小决定区域的颜色 % 假设有一系列的数据点 Arand(5,6); %A为绘图的数据,数据大小决定颜色 wei_shu%.3f; %代表数据保留三位小…...
Docker Desktop 的安装与汉化指南
前言 Docker Desktop 是一款非常流行的开发工具,它使得开发者能够在自己的计算机上轻松地构建、运行和调试 Docker 容器。然而,默认情况下,Docker Desktop 的界面是英文的,对于中文用户来说,有时候会觉得不够友好。幸…...
前端form表单+ifarme方式实现大文件下载
// main.jsimport Vue from vue; import App from ./App.vue; import { downloadTokenFile } from /path/to/your/function; // 替换为您的函数路径// 将 downloadTokenFile 添加到 Vue 原型上 Vue.prototype.$downloadTokenFile downloadTokenFile;new Vue({el: #app,render:…...
Leetcode面试经典150题-141.环形链表
题目比较简单,重点是理解思想 解法都在代码里,不懂就留言或者私信 /*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/ public…...
sh文件执行提示语法错误: 未预期的文件结尾
在执行sh文件时总是提示:语法错误: 未预期的文件结尾,尝试删除最后的空格也不对 最后发现在notepad中转换的问题 需要把windows换成unix就行了...
基于SpringBoot的甜品店管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于JavaSpringBootVueMySQL的蛋糕甜品店管理系…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
