给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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;
}
};
												

最新文章

  1. javascript的api设计原则
  2. 感恩回馈,新鲜出炉的《ASP.NET MVC 5框架揭秘》免费赠送
  3. PL/SQL Developer记住用户名密码
  4. 使用gson解析,生成Json
  5. Java从零开始学四十七(注解简述)
  6. 一个Java程序员应该掌握的10项技能
  7. IOC主要接口
  8. CentOS 6一键系统优化 Shell 脚本
  9. sql中的 IF 条件语句的用法
  10. 数据库学习之MySQL进阶
  11. 【转载】MySQL5.7 添加用户、删除用户与授权
  12. js form表单的校验
  13. ActionFilterAttribute 全局记录API日志
  14. 解决y7000笔记本ubuntu下wifi无法连接问题
  15. Codeforces 420D Cup Trick 平衡树
  16. python 格式化字符串&quot;%s&quot;%
  17. py库: PIL 、pillow(图像处理)
  18. ZOJ Monthly, March 2018 题解
  19. 利用阿里云如何开发一款直播app?
  20. vue-cli中引入jquery

热门文章

  1. 那些你常用的JSP知识
  2. scss-嵌套规则
  3. HTML字符实体名称/实体编号
  4. js实现图片延时加载的原理
  5. Format - DateTime
  6. Python学习系列----第六章 数据结构
  7. SharePoint 2010配置PDF文件全文检索
  8. How To Capture Packets with TCPDUMP?
  9. 林锐书:写一个hello world by seasoned professional
  10. nautilus命令