codingwhite
diff --git a/‎src/main/java/com/fishercoder/solutions/_109.java
Lines changed: 22 additions & 17 deletions b/‎src/main/java/com/fishercoder/solutions/_109.java
Lines changed: 22 additions & 17 deletions
diff --git a/‎src/test/java/com/fishercoder/_109Test.java
Lines changed: 36 additions & 0 deletions b/‎src/test/java/com/fishercoder/_109Test.java
Lines changed: 36 additions & 0 deletions
@@ -4,29 +4,34 @@
 import com.fishercoder.common.classes.TreeNode;
 
 /**
+ * 109. Convert Sorted List to Binary Search Tree
+ *
  * Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
  */
 public class _109 {
 
-    public TreeNode sortedListToBST(ListNode head) {
-        return rec(head, null);
-    }
+    public static class Solution1 {
 
-    public TreeNode rec(ListNode start, ListNode end) {
-        if (start == end) {
-            return null;
-        } else {
-            ListNode mid = start;
-            ListNode probe = start;
-            while (probe != end && probe.next != end) {
-                mid = mid.next;
-                probe = probe.next.next;
-            }
+        public TreeNode sortedListToBST(ListNode head) {
+            return toBstRecursively(head, null);
+        }
 
-            TreeNode root = new TreeNode(mid.val);
-            root.left = rec(start, mid);
-            root.right = rec(mid.next, end);
-            return root;
+        public TreeNode toBstRecursively(ListNode start, ListNode end) {
+            if (start == end) {
+                return null;
+            } else {
+                ListNode mid = start;
+                ListNode fast = start;
+                while (fast != end && fast.next != end) {
+                    mid = mid.next;
+                    fast = fast.next.next;
+                }
+
+                TreeNode root = new TreeNode(mid.val);
+                root.left = toBstRecursively(start, mid);
+                root.right = toBstRecursively(mid.next, end);
+                return root;
+            }
         }
     }
 
 
@@ -0,0 +1,36 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.ListNode;
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.LinkedListUtils;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._109;
+import org.junit.Before;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+public class _109Test {
+    private static _109.Solution1 solution1;
+    private static ListNode head;
+    private static TreeNode expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _109.Solution1();
+    }
+
+    @Before
+    public void setUp() throws Exception {
+    }
+
+    @Test
+    public void test1() {
+        head = LinkedListUtils.contructLinkedList(new int[]{1, 2, 3, 4, 5});
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, 4, null, 2, null, 5));
+        /**as long as it's a height-balanced tree, it's good for this problem requirement*/
+        TreeUtils.printBinaryTree(solution1.sortedListToBST(head));
+    }
+
+}