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

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;}
}

http://www.lryc.cn/news/437960.html

相关文章:

  • [数据集][目标检测]河道垃圾检测数据集VOC+YOLO格式2274张8类别
  • python vtk 绘制圆柱体和包围盒
  • Fisco Bcos 2.11.0通过网络和本地二进制文件搭建单机节点联盟链网络(搭建你的第一个区块链网络)
  • 【Canvas与表盘】绘制黄蓝两色简约表盘
  • 大数据-128 - Flink 并行度设置 细节详解 全局、作业、算子、Slot
  • 图新地球-将地图上大量的地标点批量输出坐标到csv文件【kml转excel】
  • Git提交有乱码
  • leetcode hot100_part4_子串
  • Spring Cloud之三 网关 Gateway
  • Linux 进程1
  • LeetCode: 2552. 统计上升四元组 动态规划 时间复杂度O(n*n)
  • Unity 编辑器设置中文
  • springboot-创建连接池
  • matlab绘制不同区域不同色彩的图,并显示数据(代码)
  • Docker Desktop 的安装与汉化指南
  • 前端form表单+ifarme方式实现大文件下载
  • Leetcode面试经典150题-141.环形链表
  • sh文件执行提示语法错误: 未预期的文件结尾
  • 基于SpringBoot的甜品店管理系统
  • 动态规划-不同的子序列
  • 如何通过OceanBase的多级弹性扩缩容能力应对业务洪峰
  • D - 1D Country(AtCoder Beginner Contest 371)
  • 怎么很多张图片拼接成一张?试试这几种图片拼接方法!
  • Python实现优化的分水岭算法
  • 智慧交通基于yolov8的行人车辆检测计数系统python源码+onnx模型+精美GUI界面
  • Linux开发工具的使用
  • 【devops】devops-git之介绍以及日常使用
  • 012复杂度07leetcode
  • 4.网络编程
  • OpenCV GUI常用函数详解