package leetcode;

/**
 * https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
 */
public class Problem109 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode sortedListToBST(ListNode head) {
        // TODO: to be implemented
        return null;
    }
    
    public static void main(String[] args) {
        Problem109 prob = new Problem109();
    }
}

@@ -12,16 +12,68 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A * h
@@ -484,32 +484,64 @@
        %7D%0A    %7D%0A%0A
+    private TreeNode root;%0A    %0A
     public TreeN
@@ -589,34 +589,207 @@
     
-// TODO: to be implemented
+List%3CListNode%3E listNodes = new ArrayList%3C%3E();%0A        for (ListNode n = head; n != null; n = n.next) %7B%0A            listNodes.add(n);%0A        %7D%0A        sortedListToBST(listNodes, 0, listNodes.size());
 %0A   
@@ -800,20 +800,20 @@
  return 
-null
+root
 ;%0A    %7D%0A
@@ -826,90 +826,746 @@
    p
-ublic static void main(String%5B%5D args) %7B%0A        Problem109 prob = new Problem109()
+rivate void sortedListToBST(List%3CListNode%3E listNodes, int lo, int hi) %7B%0A        if (lo %3E= hi) %7B%0A            return;%0A        %7D%0A        int mid = (int) Math.ceil((hi + lo) / 2);%0A        int val = listNodes.get(mid).val;%0A        if (root == null) %7B%0A            root = new TreeNode(val);%0A        %7D else %7B%0A            add(root, val);%0A        %7D%0A        sortedListToBST(listNodes, lo, mid);%0A        sortedListToBST(listNodes, mid+1, hi);%0A    %7D%0A    %0A    private TreeNode add(TreeNode node, int val) %7B%0A        if (node == null) %7B%0A            return new TreeNode(val);%0A        %7D%0A        if (val %3C= node.val) %7B%0A            node.left = add(node.left, val);%0A        %7D else %7B%0A            node.right = add(node.right, val);%0A        %7D%0A        return node
 ;%0A  

Solve problem 109