add a solution for 1110

fishercoder1534 · fishercoder1534 · commit fb2a18c780af · 2024-07-17T07:20:34.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/secondthousand/_1110.java b/src/main/java/com/fishercoder/solutions/secondthousand/_1110.java
@@ -3,9 +3,11 @@
 import com.fishercoder.common.classes.TreeNode;
 
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
+import java.util.Set;
 
 public class _1110 {
     public static class Solution1 {
@@ -72,4 +74,54 @@ private boolean delete(TreeNode curr, int toDelete, Queue<TreeNode> queue) {
             }
         }
     }
+
+    public static class Solution2 {
+        //use BFS
+        public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
+            Set<Integer> deleteSet = new HashSet<>();
+            for (int d : toDelete) {
+                deleteSet.add(d);
+            }
+            Queue<TreeNode> q = new LinkedList<>();
+            q.offer(root);
+            List<TreeNode> forest = new ArrayList<>();
+            while (!q.isEmpty()) {
+                TreeNode curr = q.poll();
+
+                //process left child if any
+                if (curr.left != null) {
+                    //add it into the q first because we need to process it any ways as it might have children that might not need to be deleted
+                    q.offer(curr.left);
+                    if (deleteSet.contains(curr.left.val)) {
+                        curr.left = null;
+                    }
+                }
+
+                //process right child if any
+                if (curr.right != null) {
+                    q.offer(curr.right);
+                    if (deleteSet.contains(curr.right.val)) {
+                        curr.right = null;
+                    }
+                }
+
+                //process this curr node: if it needs to be deleted, then add its non-null children into forest as we checked its children
+                // and we know they do not need to be deleted at this point
+                if (deleteSet.contains(curr.val)) {
+                    if (curr.left != null) {
+                        forest.add(curr.left);
+                    }
+                    if (curr.right != null) {
+                        forest.add(curr.right);
+                    }
+                }
+                //we don't add curr into forest here, otherwise there might be duplicate as we might have added them as their parent's child already
+            }
+            //at this point, only root might be missing, so we check root
+            if (!deleteSet.contains(root.val)) {
+                forest.add(root);
+            }
+            return forest;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/secondthousand/_1110Test.java b/src/test/java/com/fishercoder/secondthousand/_1110Test.java
@@ -3,21 +3,22 @@
 import com.fishercoder.common.classes.TreeNode;
 import com.fishercoder.common.utils.TreeUtils;
 import com.fishercoder.solutions.secondthousand._1110;
-import org.junit.BeforeClass;
-import org.junit.Test;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.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 _1110.Solution2 solution2;
     private static TreeNode root;
 
-    @BeforeClass
-    public static void setup() {
+    @BeforeEach
+    public void setup() {
         solution1 = new _1110.Solution1();
+        solution2 = new _1110.Solution2();
     }
 
     @Test
@@ -28,6 +29,12 @@ public void test1() {
         for (TreeNode node : actual) {
             TreeUtils.printBinaryTree(node);
         }
+        actual.clear();
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
+        actual = solution2.delNodes(root, new int[]{3, 5});
+        for (TreeNode node : actual) {
+            TreeUtils.printBinaryTree(node);
+        }
     }
 
     @Test
@@ -38,5 +45,11 @@ public void test2() {
         for (TreeNode node : actual) {
             TreeUtils.printBinaryTree(node);
         }
+        actual.clear();
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, null, 4, 3));
+        actual = solution2.delNodes(root, new int[]{2, 3});
+        for (TreeNode node : actual) {
+            TreeUtils.printBinaryTree(node);
+        }
     }
 }
