Convert Linked List to Balanced Binary Search Tree

ConvertLinkedListToBalancedBST.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
    
         ListNode curr = head;
         while (curr != null){
             arr.add(curr.val);
             curr = curr.next;
         }
         
         return helper(arr, 0, arr.size() - 1);
        
    }
    
    public TreeNode helper(ArrayList<Integer> arr, int left, int right){
        if (left > right) return null;
        
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(arr.get(mid));
        node.left = helper(arr, left, mid-1);
        node.right = helper(arr, mid+1, right);
        
        return node;
    }
}



//Alternate implementation, bottom up creation of BST

public class Solution {
    private ListNode cur;
    public TreeNode sortedListToBST(ListNode head) {
        cur = head;
        return generate(count(head));
    }
    private TreeNode generate(int n){
        if (0 == n)
            return null;
        TreeNode node = new TreeNode(0);
        node.left = generate(n/2);
        node.val = cur.val;
        cur = cur.next;
        node.right = generate(n-n/2-1);
        return node;
    }
    private int count(ListNode h){
        int size = 0;
        while (h != null){
            ++size;
            h = h.next;
        }
        return size;
    }
}