[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 balanced BST.

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; next = null; }
 7  * }
 8  */
 9 /**
10  * Definition for binary tree
11  * public class TreeNode {
12  *     int val;
13  *     TreeNode left;
14  *     TreeNode right;
15  *     TreeNode(int x) { val = x; }
16  * }
17  */
18 public class Solution {
19     public TreeNode sortedListToBST(ListNode head) {
20         return mySortedListToBST(head, getLength(head));
21     }
22 
23     private TreeNode mySortedListToBST(ListNode head, int length) {
24         // TODO Auto-generated method stub
25         if (head == null || length == 0)
26             return null;
27         if (length == 1)
28             return new TreeNode(head.val);
29         int mid = length / 2;
30         ListNode peak = head;
31         for (int i = 0; i < mid; ++i) {
32             peak = peak.next;
33         }
34         TreeNode root=new TreeNode(peak.val);
35         root.left=mySortedListToBST(head, mid);
36         root.right=mySortedListToBST(peak.next, length-mid-1);
37         return root;
38     }
39 
40     private int getLength(ListNode head) {
41         // TODO Auto-generated method stub
42         int length = 0;
43         while (head != null) {
44             head = head.next;
45             length++;
46         }
47         return length;
48 }
49 }

-------------------------------------------------------------------------------------------

20150215

这个写法（从上到下地来构造这棵树）有点问题：因为现在我无法在O（1）的时间内获取元素，每回都得从头开始遍历一遍，找到中间的才行。因此，我们应该要能够想到得从下到上的来构造这棵树(Each time you are stucked with the top-down approach, give bottom-up a try. )，这样的话，我们能够做到：The bottom-up approach enables us to access the list in its order at the same time as creating nodes.

http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; next = null; }
 7  * }
 8  */
 9 /**
10  * Definition for binary tree
11  * public class TreeNode {
12  *     int val;
13  *     TreeNode left;
14  *     TreeNode right;
15  *     TreeNode(int x) { val = x; }
16  * }
17  */
18 public class Solution {
19     ListNode cur;
20     public TreeNode sortedListToBST(ListNode head) {
21         if(head==null)
22             return null;
23         ListNode runner=head;
24         int size=1;
25         cur=head;
26         while(runner.next!=null){
27             runner=runner.next;
28             size++;
29         }
30         return makeTree(0,size-1);
31     }
32     public TreeNode makeTree(int start,int end){
33         if(start>end)
34             return null;
35         if(start==end){
36             TreeNode temp= new TreeNode(cur.val);
37             cur=cur.next;
38             return temp;
39         }
40         int mid=start+(end-start)/2;
41         TreeNode left=makeTree(start,mid-1);
42         TreeNode root=new TreeNode(cur.val);
43         root.left=left;
44         cur=cur.next;
45         TreeNode right=makeTree(mid+1,end);
46         root.right=right;
47         return root;
48     }
49 }