LeetCode109 将有序链表转为二叉搜索树
2024-10-19 03:51:37
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0
/ \
-3 9
/ /
-10 5
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
算法思想:
和之前那道将有序数组转为二叉搜索树思路完全一样,只不过是操作的数据类型有所差别,一个是数组,一个是链表。数组方便就方便在可以通过index直接访问任意一个元素,而链表不行。由于二分查找法每次需要找到中点,而链表的查找中间点可以通过快慢指针来操作,找到中点后,要以中点的值建立一个数的根节点,然后需要把原链表断开,分为前后两个链表,都不能包含原中节点,然后再分别对这两个链表递归调用原函数,分别连上左右子节点即可。
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if (!head)
return NULL;
if (!head->next)
return new TreeNode(head->val);
ListNode *slow = head;
ListNode *fast = head;
ListNode *last = slow; //记录中间点
while (fast->next && fast->next->next) { //利用双指针找链表中间点
last = slow;
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next; //把原链表断开,分为前后两个链表,都不能包含原中间点
last->next = NULL;
TreeNode *cur = new TreeNode(slow->val);
if (head != slow)
cur->left = sortedListToBST(head);
cur->right = sortedListToBST(fast);
return cur;
}
};
最新文章
- PHP 下option selected 无效
- SQL Server 2008 R2 安装出错:Could not open key
- 前端自动化工具 -- grunt 使用简介
- GDB代码调试与使用
- CentOS 6.4 搭建SVN服务器
- 存储过程系列之存储过程sql查询存储过程的使用
- java短路问题
- Java DB 访问之 mybatis mapper xml 配置方式
- 手把手教你撸一个 Webpack Loader
- JavaScript 面向对象之原型对象
- 学习笔记CB013: TensorFlow、TensorBoard、seq2seq
- Balanced Sequence HDU - 6299(杭电多校1 B)
- 解决binwalk运行提示缺少LZMA模块
- iOS自定义结构体
- linux下socket编程常用头文件
- 【转】struts2.5框架使用通配符指定方法(常见错误)
- 编程笔记:JavaScript 中的类型检查
- idea破解方法
- TreeSet中自定义Comparator实现降序
- php获取微信token和ticket并返回签名