add 1382

fishercoder1534 · fishercoder1534 · commit 6c39b9cbebd6 · 2020-03-14T21:48:17.000-07:00
diff --git a/README.md b/README.md
@@ -8,7 +8,8 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
-|1381|[Design a Stack With Increment Operation](https://leetcode.com/problems/design-a-stack-with-increment-operation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1381.java) | |Easy|Stack, Design|
+|1382|[Design a Stack With Increment Operation](https://leetcode.com/problems/balance-a-binary-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1382.java) | |Medium|Binary Search Tree|
+|1381|[Design a Stack With Increment Operation](https://leetcode.com/problems/design-a-stack-with-increment-operation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1381.java) | |Medium|Stack, Design|
 |1380|[Lucky Numbers in a Matrix](https://leetcode.com/problems/lucky-numbers-in-a-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1380.java) | |Easy|Array|
 |1379|[Find a Corresponding Node of a Binary Tree in a Clone of That Tree](https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1379.java) | |Medium|Tree|
 |1377|[Frog Position After T Seconds](https://leetcode.com/problems/frog-position-after-t-seconds/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1377.java) | |Hard|DFS, BFS|
diff --git a/src/main/java/com/fishercoder/solutions/_1382.java b/src/main/java/com/fishercoder/solutions/_1382.java
@@ -0,0 +1,51 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * 1382. Balance a Binary Search Tree
+ *
+ * Given a binary search tree, return a balanced binary search tree with the same node values.
+ * A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.
+ * If there is more than one answer, return any of them.
+ *
+ * Example 1:
+ * Input: root = [1,null,2,null,3,null,4,null,null]
+ * Output: [2,1,3,null,null,null,4]
+ * Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.
+ *
+ * Constraints:
+ * The number of nodes in the tree is between 1 and 10^4.
+ * The tree nodes will have distinct values between 1 and 10^5.
+ * */
+public class _1382 {
+    public static class Solution1 {
+        public TreeNode balanceBST(TreeNode root) {
+            List<Integer> inorder = inorder(root, new ArrayList<>());
+            return dfs(inorder, 0, inorder.size() - 1);
+        }
+
+        private List<Integer> inorder(TreeNode root, List<Integer> list) {
+            if (root == null) {
+                return list;
+            }
+            inorder(root.left, list);
+            list.add(root.val);
+            return inorder(root.right, list);
+        }
+
+        private TreeNode dfs(List<Integer> nums, int start, int end) {
+            if (end < start) {
+                return null;
+            }
+            int mid = (start + end) / 2;
+            TreeNode root = new TreeNode(nums.get(mid));
+            root.left = dfs(nums, start, mid - 1);
+            root.right = dfs(nums, mid + 1, end);
+            return root;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1382Test.java b/src/test/java/com/fishercoder/_1382Test.java
@@ -0,0 +1,26 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1382;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+public class _1382Test {
+    private static _1382.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1382.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, null, 2, null, 3, null, 4, null, null));
+        TreeUtils.printBinaryTree(root);
+        TreeUtils.printBinaryTree(solution1.balanceBST(root));
+    }
+
+}
