Convert Sorted List to Binary Search Tree.java

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
     
    private ListNode node;
    
    public TreeNode sortedListToBST(ListNode head) {  
        // write your code here
        int listSize = 0;
        node = head;
        listSize = getListSize(head);
        TreeNode resultTree = sortedListToBSTHelper(listSize);
        
        return resultTree;
    }
    
    public int getListSize(ListNode head) {
        int listSize = 0;
        while (head != null) {
            listSize++;
            head = head.next;
        }
        return listSize;
    }
    
    public TreeNode sortedListToBSTHelper(int listSize) {
        if (listSize <= 0) {
            return null;
        }
        TreeNode leftTree = sortedListToBSTHelper(listSize / 2);
        TreeNode root = new TreeNode(node.val);
        node = node.next;
        TreeNode rightTree = sortedListToBSTHelper(listSize - 1 - listSize / 2);
        
        root.left = leftTree;
        root.right = rightTree;
        
        return root;
    }
}