add 1110

fishercoder1534 · fishercoder1534 · commit 6a5e6a3b4509 · 2020-12-03T10:42:54.000-08:00
diff --git a/README.md b/README.md
@@ -243,6 +243,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1119|[Remove Vowels from a String](https://leetcode.com/problems/remove-vowels-from-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1119.java) |  [:tv:](https://www.youtube.com/watch?v=6KCBrIWEauw)|Easy||
 |1118|[Number of Days in a Month](https://leetcode.com/problems/number-of-days-in-a-month/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1118.java) | |Easy||
 |1114|[Print in Order](https://leetcode.com/problems/print-in-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1114.java) | |Easy||
+|1110|[Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1110.java) | |Medium|Tree, DFS|
 |1108|[Defanging an IP Address](https://leetcode.com/problems/defanging-an-ip-address/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1108.java) |  [:tv:](https://www.youtube.com/watch?v=FP0Na-pL0qk)|Easy||
 |1104|[Path In Zigzag Labelled Binary Tree](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1104.java) | |Medium|Math, Tree|
 |1103|[Distribute Candies to People](https://leetcode.com/problems/distribute-candies-to-people/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1103.java) | |Easy|Math|
diff --git a/src/main/java/com/fishercoder/solutions/_1110.java b/src/main/java/com/fishercoder/solutions/_1110.java
@@ -0,0 +1,75 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+public class _1110 {
+    public static class Solution1 {
+        public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
+            Queue<TreeNode> queue = new LinkedList<>();
+            queue.offer(root);
+            for (int d : to_delete) {
+                delete(d, queue);
+            }
+            List<TreeNode> result = new ArrayList<>();
+            while (!queue.isEmpty()) {
+                result.add(queue.poll());
+            }
+            return result;
+        }
+
+        private void delete(int toDelete, Queue<TreeNode> queue) {
+            int size = queue.size();
+            for (int i = 0; i < size; i++) {
+                TreeNode curr = queue.poll();
+                if (delete(curr, toDelete, queue)) {
+                    if (toDelete != curr.val) {
+                        queue.offer(curr);
+                    }
+                    break;
+                } else {
+                    queue.offer(curr);
+                }
+            }
+        }
+
+        private boolean delete(TreeNode curr, int toDelete, Queue<TreeNode> queue) {
+            if (curr == null) {
+                return false;
+            } else {
+                if (curr.val == toDelete) {
+                    if (curr.left != null) {
+                        queue.offer(curr.left);
+                    }
+                    if (curr.right != null) {
+                        queue.offer(curr.right);
+                    }
+                    return true;
+                } else if (curr.left != null && curr.left.val == toDelete) {
+                    if (curr.left.left != null) {
+                        queue.offer(curr.left.left);
+                    }
+                    if (curr.left.right != null) {
+                        queue.offer(curr.left.right);
+                    }
+                    curr.left = null;
+                    return true;
+                } else if (curr.right != null && curr.right.val == toDelete) {
+                    if (curr.right.left != null) {
+                        queue.offer(curr.right.left);
+                    }
+                    if (curr.right.right != null) {
+                        queue.offer(curr.right.right);
+                    }
+                    curr.right = null;
+                    return true;
+                }
+                return delete(curr.left, toDelete, queue) || delete(curr.right, toDelete, queue);
+            }
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1110Test.java b/src/test/java/com/fishercoder/_1110Test.java
@@ -0,0 +1,44 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.LinkedListUtils;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1110;
+import com.fishercoder.solutions._206;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.List;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _1110Test {
+    private static _1110.Solution1 solution1;
+    private static TreeNode root;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1110.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
+        TreeUtils.printBinaryTree(root);
+        List<TreeNode> actual = solution1.delNodes(root, new int[]{3, 5});
+        for (TreeNode node : actual) {
+            TreeUtils.printBinaryTree(node);
+        }
+    }
+
+    @Test
+    public void test2() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, null, 4, 3));
+        TreeUtils.printBinaryTree(root);
+        List<TreeNode> actual = solution1.delNodes(root, new int[]{2, 3});
+        for (TreeNode node : actual) {
+            TreeUtils.printBinaryTree(node);
+        }
+    }
+}
