Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
这回给的是List了，所以我们无法在O(1)的时间得到中间的元素，然后二分。
当然如果能使用额外的空间的话，那我们很容易开辟一个数组然后复制List中的元素，得到以个排序数组，然后用上一题的方法来求解，这样的解法是时间O(n),空间O(n)。
第二种方法呢，我们每次从头遍历到中间那个元素（事先要先遍历求得当前链表的长度），然后分开分别求左子树和右子树，每次长度为k的时候要扫描 k/2个元素来找到中间那个，因为是二分，所以时间复杂度是O(n log n)的，空间呢，是O(1)的。
但是既然有了上一题，那这一题的初衷肯定不是用上两种朴素的方法来求解的，我试了一下都能AC，但是在面试时提出这样的解法肯定是不会满意的。
有没有其他方法呢？
我们这么想递归：首先我们知道这个链表有n个节点了，那么n/2的这个元素是我们要找的树根，那么前 n/2个元素自然就是它的左子树咯~
这句话好好理解一下。
这么想：如果我们能把当前给定的n个节点建立一棵树，然后把它添加到它的父亲的孩子指针上不就完了吗，有没有有点绕~既然我们的函数能将n长的链表建立一个子树并返回，那么我们可以先把前n/2个节点建立得到左子树，然后n/2这个节点是根，然后是右子树，这样就可以自底向上在遍历链表的同时建立排序树了。
讲还是貌似讲的有点绕啊~好好理解一下吧。
看代码吧~
/**
* 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:
TreeNode *sortedListToBST(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n=getLen(head);
return construct(head,n);
}
TreeNode* construct(ListNode*& head,int n)
{
if(n==0)
return NULL;
int mid=n>>1;
TreeNode* left=construct(head,mid);
TreeNode* root=new TreeNode(head->val);
head=head->next;
root->left=left;
root->right=construct(head,n-mid-1);
return root;
}
int getLen(ListNode* head)
{
int k=0;
while(head)
{
k++;
head=head->next;
}
return k;
}
};