add a solution for 1008

fishercoder1534 · fishercoder1534 · commit 38589acda4eb · 2021-10-13T07:51:58.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_1008.java b/src/main/java/com/fishercoder/solutions/_1008.java
@@ -23,4 +23,30 @@ private TreeNode bstFromPreorder(int[] preorder, int bound) {
             return root;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * I'm happy to have come up with this solution completely on my own on 10/13/2021.Enjoy the beauty of recursion!
+         */
+        public TreeNode bstFromPreorder(int[] preorder) {
+            return bstFromPreorder(preorder, 0, preorder.length);
+        }
+
+        private TreeNode bstFromPreorder(int[] preorder, int start, int end) {
+            if (start >= end) {
+                return null;
+            }
+            TreeNode root = new TreeNode(preorder[start]);
+            int i = start + 1;
+            for (; i < end; i++) {
+                if (preorder[i] > preorder[start]) {
+                    break;
+                }
+            }
+            root.left = bstFromPreorder(preorder, start + 1, i);
+            root.right = bstFromPreorder(preorder, i, end);
+            return root;
+        }
+
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1008Test.java b/src/test/java/com/fishercoder/_1008Test.java
@@ -11,19 +11,24 @@
 
 public class _1008Test {
     private static _1008.Solution1 solution1;
+    private static _1008.Solution2 solution2;
     private static int[] preorder;
     private static TreeNode expected;
     private static TreeNode actual;
 
     @Test
     public void test1() {
         solution1 = new _1008.Solution1();
+        solution2 = new _1008.Solution2();
         preorder = new int[]{8, 5, 1, 7, 10, 12};
         expected = TreeUtils.constructBinaryTree(Arrays.asList(8, 5, 10, 1, 7, null, 12));
         TreeUtils.printBinaryTree(expected);
         actual = solution1.bstFromPreorder(preorder);
         TreeUtils.printBinaryTree(actual);
         assertEquals(expected, actual);
+        actual = solution2.bstFromPreorder(preorder);
+        TreeUtils.printBinaryTree(actual);
+        assertEquals(expected, actual);
     }
 
 }
