Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution：Recusive 选中点 并左右递归建立
思路：快慢指针找到中点后，左右递归建立
递归input: start, end; return: 建好的头结点
Time Complexity: O(n logn) Space Complexity: O(logN) 递归缓存
Solution1 Code：
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
return toBST(head, null);
}
public TreeNode toBST(ListNode head, ListNode tail){
if(head == tail) return null;
// use slow to find mid,
ListNode slow = head;
ListNode fast = head;
while(fast != tail && fast.next != tail){
fast = fast.next.next;
slow = slow.next;
}
// recursively build
TreeNode node = new TreeNode(slow.val);
node.left = toBST(head, slow);
node.right = toBST(slow.next, tail);
return node;
}
}
