LeetCode 中级 - 有序链表转换二叉搜索树(109)
2024-09-22 06:13:27
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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) {}
* };
*/
class Solution {
public:
vector<int> v;
TreeNode* sortedListToBST(ListNode* head) {
//遍历链表将值存入vector中,方便之后的查中间值操作。
while(head!=NULL)
{
v.push_back(head->val);
head=head->next;
}
return dfs(,v.size()-);
}
TreeNode * dfs(int l,int r)
{
if(l>r) return NULL;
int mid=l+(r-l)/;
TreeNode *root=new TreeNode(v[mid]);
root->left=dfs(l,mid-);
root->right=dfs(mid+,r);
return root;
}
};
最新文章
- javascript的api设计原则
- 感恩回馈,新鲜出炉的《ASP.NET MVC 5框架揭秘》免费赠送
- PL/SQL Developer记住用户名密码
- 使用gson解析,生成Json
- Java从零开始学四十七(注解简述)
- 一个Java程序员应该掌握的10项技能
- IOC主要接口
- CentOS 6一键系统优化 Shell 脚本
- sql中的 IF 条件语句的用法
- 数据库学习之MySQL进阶
- 【转载】MySQL5.7 添加用户、删除用户与授权
- js form表单的校验
- ActionFilterAttribute 全局记录API日志
- 解决y7000笔记本ubuntu下wifi无法连接问题
- Codeforces 420D Cup Trick 平衡树
- python 格式化字符串";%s";%
- py库: PIL 、pillow(图像处理)
- ZOJ Monthly, March 2018 题解
- 利用阿里云如何开发一款直播app?
- vue-cli中引入jquery