Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution：Recusive 選中點(diǎn) 并左右遞歸建立
思路：快慢指針找到中點(diǎn)后开瞭，左右遞歸建立
遞歸input: start, end; return: 建好的頭結(jié)點(diǎn)
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;
}
}
