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的蛋糕甜品店管理系…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
Python训练营-Day26-函数专题1:函数定义与参数
题目1:计算圆的面积 任务: 编写一个名为 calculate_circle_area 的函数,该函数接收圆的半径 radius 作为参数,并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求:函数接收一个位置参数 radi…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
