109. Convert Sorted List to Bina

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/

只要 items 数目确定，所生成的Balanced BST 的 structure 是可以确定的，no matter items in array or list.

对该确定的 Balanced BST 使用 inorder traversal，同时遍历 List 对当前处的 TreeNode 进行赋值就好了。

class Solution {
    ListNode currentListNode = null;
    
    public TreeNode sortedListToBST(ListNode head) {
        int size = getListLength(head);
        currentListNode = head;
        
        return inorderGenerator(size);
    }
    
    private TreeNode inorderGenerator(int len) {
        if (len == 0) {
            return null;
        }
        int half = len / 2;
        TreeNode leftChild = inorderGenerator(half);
        TreeNode root = new TreeNode(currentListNode.val);
        currentListNode = currentListNode.next;
        TreeNode rightChild = inorderGenerator(len - half -1); //这里的减1，是因为 root 已经占了一个 Node
        root.left = leftChild;
        root.right = rightChild;
        
        return root;
    }
    
    private int getListLength(ListNode head) {
        int size = 0;
        ListNode runner = head;
        while (runner != null) {
            size++;
            runner = runner.next;
        }
        return size;
    }
}