Question:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example:
21->2->3 => / \ 1 3
Analysis:
有一道相似的题 “Convert Sorted Array to Balanced BST” ，解法是先找到数组的中间点，也就是树的根，然后递归地构建左子树和右子树，自上而下依次插入节点。用这种解法依赖于数组的index，因为每次递归需要找到数组的中间点来确定根的值。在数组中访问任意节点耗时O(1)。然而在linked list中，只能从头走到尾，因此找到中点耗时O(n)，对比发现慢了许多。
我们想到，对于BST，中序遍历的结果是一个从小到大的有序序列。那么如果反过来，从左到右遍历linked list，利用类似中序遍历的方式构建BST应该可行。从下到上构建这棵树，用一个curt变量记录链表的当前节点。其中helper函数的定义是：将curt指针开头的，从start到end的list转变为BST，事后curt指针指向下一个node。
Code:
1 /** 2 * Definition for ListNode. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int val) { 7 * this.val = val; 8 * this.next = null; 9 * }10 * }11 * Definition of TreeNode:12 * public class TreeNode {13 * public int val;14 * public TreeNode left, right;15 * public TreeNode(int val) {16 * this.val = val;17 * this.left = this.right = null;18 * }19 * }20 */ 21 public class Solution {22 /**23 * @param head: The first node of linked list.24 * @return: a tree node25 */26 private ListNode curt = null;27 28 public TreeNode sortedListToBST(ListNode head) { 29 if(head == null) {30 return null;31 }32 33 curt = head;34 int length = getListLength(head);35 return helper(0, length - 1);36 }37 38 private int getListLength(ListNode head) {39 int length = 0;40 while(head != null) {41 head = head.next;42 length++;43 }44 return length;45 }46 47 private TreeNode helper(int start, int end) {48 if(start > end) {49 return null;50 }51 52 int mid = start + (end - start) / 2;53 TreeNode left = helper(start, mid - 1);54 55 TreeNode root = new TreeNode(curt.val);56 curt = curt.next;57 58 TreeNode right = helper(mid + 1, end);59 60 root.left = left;61 root.right = right;62 63 return root;64 }65 }
Complexity：
时间复杂度为O(n)，n为树中节点的个数。
（如果用找中点的方法从上往下构建树，树高为logn，每一层找中点耗费O(n)时间，所以总共时间复杂度为O(n * logn)）