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

2024-05-06 21:28

本文主要是介绍力扣每日一题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:有序链表转换二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/965419

相关文章

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

C语言中自动与强制转换全解析

《C语言中自动与强制转换全解析》在编写C程序时,类型转换是确保数据正确性和一致性的关键环节,无论是隐式转换还是显式转换,都各有特点和应用场景,本文将详细探讨C语言中的类型转换机制,帮助您更好地理解并在... 目录类型转换的重要性自动类型转换(隐式转换)强制类型转换(显式转换)常见错误与注意事项总结与建议类型

Python实现视频转换为音频的方法详解

《Python实现视频转换为音频的方法详解》这篇文章主要为大家详细Python如何将视频转换为音频并将音频文件保存到特定文件夹下,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5. 注意事项

使用Python实现图片和base64转换工具

《使用Python实现图片和base64转换工具》这篇文章主要为大家详细介绍了如何使用Python中的base64模块编写一个工具,可以实现图片和Base64编码之间的转换,感兴趣的小伙伴可以了解下... 简介使用python的base64模块来实现图片和Base64编码之间的转换。可以将图片转换为Bas

Linux使用dd命令来复制和转换数据的操作方法

《Linux使用dd命令来复制和转换数据的操作方法》Linux中的dd命令是一个功能强大的数据复制和转换实用程序,它以较低级别运行,通常用于创建可启动的USB驱动器、克隆磁盘和生成随机数据等任务,本文... 目录简介功能和能力语法常用选项示例用法基础用法创建可启动www.chinasem.cn的 USB 驱动

Python 标准库time时间的访问和转换问题小结

《Python标准库time时间的访问和转换问题小结》time模块为Python提供了处理时间和日期的多种功能,适用于多种与时间相关的场景,包括获取当前时间、格式化时间、暂停程序执行、计算程序运行时... 目录模块介绍使用场景主要类主要函数 - time()- sleep()- localtime()- g

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法,它将时间划分为若干个固定大小的窗口,每个窗口内记录了该时间

Java将时间戳转换为Date对象的方法小结

《Java将时间戳转换为Date对象的方法小结》在Java编程中,处理日期和时间是一个常见需求,特别是在处理网络通信或者数据库操作时,本文主要为大家整理了Java中将时间戳转换为Date对象的方法... 目录1. 理解时间戳2. Date 类的构造函数3. 转换示例4. 处理可能的异常5. 考虑时区问题6.