refactor 701

fishercoder1534 · fishercoder1534 · commit 93ad4de15ce1 · 2021-09-29T09:56:22.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_701.java b/src/main/java/com/fishercoder/solutions/_701.java
@@ -2,6 +2,9 @@
 
 import com.fishercoder.common.classes.TreeNode;
 
+import java.util.ArrayList;
+import java.util.List;
+
 public class _701 {
     public static class Solution1 {
         public TreeNode insertIntoBST(TreeNode root, int val) {
@@ -16,4 +19,47 @@ public TreeNode insertIntoBST(TreeNode root, int val) {
             return root;
         }
     }
+
+    public static class Solution2 {
+        public TreeNode insertIntoBST(TreeNode root, int val) {
+            List<Integer> list = new ArrayList<>();
+            inorder(root, list);
+            int insertionPoint = binarySearch(list, val);
+            list.add(insertionPoint, val);
+            return formBST(list);
+        }
+
+        private TreeNode formBST(List<Integer> list) {
+            if (list.isEmpty()) {
+                return null;
+            }
+            TreeNode newRoot = new TreeNode(list.get(list.size() / 2));
+            newRoot.left = formBST(list.subList(0, list.size() / 2));
+            newRoot.right = formBST(list.subList(list.size() / 2 + 1, list.size()));
+            return newRoot;
+        }
+
+        private int binarySearch(List<Integer> list, int target) {
+            int left = 0;
+            int right = list.size() - 1;
+            while (left < right) {
+                int mid = left + (right - left) / 2;
+                if (list.get(mid) < target) {
+                    left = mid + 1;
+                } else {
+                    right = mid - 1;
+                }
+            }
+            return left == right ? list.get(left) >= target ? left : left + 1 : left;//here's the most tricky/easy to get buggy part!
+        }
+
+        private void inorder(TreeNode root, List<Integer> list) {
+            if (root == null) {
+                return;
+            }
+            inorder(root.left, list);
+            list.add(root.val);
+            inorder(root.right, list);
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_701Test.java b/src/test/java/com/fishercoder/_701Test.java
@@ -0,0 +1,45 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._701;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+public class _701Test {
+    private static _701.Solution1 solution1;
+    private static _701.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _701.Solution1();
+        solution2 = new _701.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        int val = 88;
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(61, 46, 66, 43, null, null, null, 39, null, null, null));
+        TreeUtils.printBinaryTree(root);
+        TreeUtils.printBinaryTree(solution1.insertIntoBST(root, val));
+    }
+
+    @Test
+    public void test2() {
+        int val = 88;
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(61, 46, 66, 43, null, null, null, 39, null, null, null));
+        TreeUtils.printBinaryTree(root);
+        TreeUtils.printBinaryTree(solution2.insertIntoBST(root, val));
+    }
+
+    @Test
+    public void test3() {
+        int val = 5;
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(4, 2, 7, 1, 3));
+        TreeUtils.printBinaryTree(root);
+        TreeUtils.printBinaryTree(solution2.insertIntoBST(root, val));
+    }
+
+}
