77 Notes:
88 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
99
10- Solution: Recursion. Pre-order. O(n)
10+ Solution: 1. Recursion. In-order. O(n)
11+ 2. Recursion . Pre-order.
12+ 3. pre-order.
1113 */
1214/**
1315 * Definition for singly-linked list.
2729 * }
2830 */
2931public class Solution {
30- public TreeNode sortedListToBST (ListNode head ) {
31- return sortedListToBSTRe (head ,null );
32+ public ListNode iter ;
33+ public TreeNode sortedListToBST_1 (ListNode head ) {
34+ iter =head ;
35+ int len =0 ;
36+ while (head !=null ) {
37+ ++len ;
38+ head =head .next ;
39+ }
40+ return sortedListToBSTRe1 (len );
41+ }
42+ public TreeNode sortedListToBSTRe1 (int len ) {
43+ if (len ==0 )return null ;
44+ int mid =len /2 ;
45+ TreeNode left =sortedListToBSTRe1 (mid );
46+ TreeNode root =new TreeNode (iter .val );
47+ root .left =left ;
48+ iter =iter .next ;
49+ root .right =sortedListToBSTRe1 (len -1 -mid );
50+ return root ;
3251 }
33- public TreeNode sortedListToBSTRe (ListNode start ,ListNode end ) {
52+ public TreeNode sortedListToBST_2 (ListNode head ) {
53+ return sortedListToBSTRe2 (head ,null );
54+ }
55+ public TreeNode sortedListToBSTRe2 (ListNode start ,ListNode end ) {
3456if (start ==end )return null ;
3557ListNode pre =null ;
3658ListNode slow =start ;
@@ -40,11 +62,11 @@ public TreeNode sortedListToBSTRe(ListNode start, ListNode end) {
4062slow =slow .next ;
4163 }
4264TreeNode node =new TreeNode (slow .val );
43- node .left =sortedListToBSTRe (start ,slow );
44- node .right =sortedListToBSTRe (slow .next ,end );
65+ node .left =sortedListToBSTRe2 (start ,slow );
66+ node .right =sortedListToBSTRe2 (slow .next ,end );
4567return node ;
4668 }
47- public TreeNode sortedListToBST_2 (ListNode head ) {
69+ public TreeNode sortedListToBST_3 (ListNode head ) {
4870if (head ==null )return null ;
4971if (head .next ==null )return new TreeNode (head .val );
5072ListNode slow =head ;
@@ -59,9 +81,9 @@ public TreeNode sortedListToBST_2(ListNode head) {
5981TreeNode node =new TreeNode (slow .val );
6082if (pre !=null ) {
6183pre .next =null ;
62- node .left =sortedListToBST (head );
84+ node .left =sortedListToBST_3 (head );
6385 }
64- node .right =sortedListToBST (fast );
86+ node .right =sortedListToBST_3 (fast );
6587return node ;
6688 }
6789}
