Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countNodeNumb(ListNode *head)
{
int count = ;
while(head)
{
count++;
head = head->next;
} return count ; }
TreeNode * BST(ListNode *head, int size)
{
if(size == ) return new TreeNode(head->val); int half = (size + )/ ; int count = ;
ListNode *pre, *p;
pre = NULL;
p = head;
while(count < half)
{
pre = p;
p = p->next;
count ++ ;
}
TreeNode *Node = new TreeNode(p->val); Node->left = half- > ? BST(head, half-) : NULL ;
Node->right = size - half > ? BST(p->next, size - half) : NULL; return Node ;
}
TreeNode *sortedListToBST(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function if(head == NULL) return NULL ; int size = countNodeNumb(head) ;
TreeNode * myNode = BST(head, size); return myNode;
}
};
LeetCode_Convert Sorted List to Binary Search Tree的更多相关文章
-
LeetCode_Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. /* ...
-
Leetcode: Convert sorted list to binary search tree (No. 109)
Sept. 22, 2015 学一道算法题, 经常回顾一下. 第二次重温, 决定增加一些图片, 帮助自己记忆. 在网上找他人的资料, 不如自己动手. 把从底向上树的算法搞通俗一些. 先做一个例子: 9 ...
-
[LeetCode] Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树
Given a singly linked list where elements are sorted in ascending order, convert it to a height bala ...
-
[LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 这道 ...
-
leetcode -- Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height bala ...
-
[Leetcode][JAVA] Convert Sorted Array to Binary Search Tree &;&; Convert Sorted List to Binary Search Tree
Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending ord ...
-
【leetcode】Convert Sorted List to Binary Search Tree
Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in as ...
-
【leetcode】Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending ord ...
-
【LeetCode OJ】Convert Sorted Array to Binary Search Tree
Problem Link: http://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ Same idea ...
随机推荐
-
well属性
Bootstrap 有一个 class 属性叫做 well,它的作用是为设定的列创造出一种视觉上的深度感(一种视觉上的效果,动手写代码体会一下).
-
使用中国版 Office 365 -- Team Site分享
Team Site(工作组网站)主要用于团队内部的协同工作,团队(组织机构)内部每个需要使用Team Site的用户都需要一个Office 365的license.但是如果我们需要将Team Site ...
-
php变量那些事:php引擎对变量声明、存储简要分析(ZVAL)
php中变量有三个基本的特性: 1.变量符号.也就是变量的名称.形象比喻,kv中的key.这个有php引擎的符号表(hash表)管理. 2.变量类型.一个php变量可以是boolean.integer ...
-
GOPS 2016全球运维大会 • 北京站概况
GOPS 2016全球运维大会上海站已圆满落幕,错过上海站的朋友或许会感到一些遗憾,但是不用担心,在12月16日,GOPS 2016全球运维大会 • 北京站将隆重召开,错过上海在的朋友可以赶上北京站哦 ...
-
this与super使用总结(java)
this: Java关键字this只能用于方法方法体内.当一个对象创建后,Java虚拟机(JVM)就会给这个对象分配一个引用自身的指针,这个指针的名字就是this.因此,this只能在类中的非静态方法 ...
-
高通QSD MSM APQ区别
高通msm是Mobile Station Modem 的缩写,即移动基带工作站,是指带有基带芯片的移动处理器,实际就是基带内置的手机处理器(soc)系列. qsd是qualcomm snapdrago ...
-
Java - 数组详解(图解数组的基本操作)
目录 什么是数组 数组的定义和内存分配 数组的赋值和访问 数组的注意事项 数组的内存图解 数组的插入 数组的删除 数组的扩容 数组的反转 首先 什么是数组 数组是一组地址连续.长度固定的具有相同类型的 ...
-
Overview of Azure Storage
Azure Storage types Blob storage. Containers for data blobs. The three types of blobs are: Page blob ...
-
Powershell获取硬件信息
1.获取系统的BIOS的信息: Get-WMIObject -Class Win32_BIOS 2.获取内存信息: Get-WMIObject -Class Win32_PhysicalMemory ...
-
让网站不去请求favicon.ico图标
让网站不去请求favicon.ico图标 favicon.ico 图标用于收藏夹图标和浏览器标签上的显示,如果不设置,浏览器会请求网站根目录的这个图标,如果网站根目录也没有这图标会产生 404.出于优 ...