力扣每日一题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

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数