add a solution for 993

fishercoder1534 · fishercoder1534 · commit 0b5535389b02 · 2021-10-19T08:17:52.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_993.java b/src/main/java/com/fishercoder/solutions/_993.java
@@ -2,8 +2,10 @@
 
 import com.fishercoder.common.classes.TreeNode;
 
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
+import java.util.Map;
 import java.util.Queue;
 import java.util.Set;
 
@@ -45,4 +47,33 @@ private boolean checkQueue(Queue<TreeNode> queue, int x, int y) {
             return set.contains(x) && set.contains(y);
         }
     }
+
+    public static class Solution2 {
+        public boolean isCousins(TreeNode root, int x, int y) {
+            Queue<TreeNode> queue = new LinkedList<>();
+            queue.offer(root);
+            Map<Integer, Integer> childToParentMap = new HashMap<>();
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                childToParentMap.clear();
+                for (int i = 0; i < size; i++) {
+                    TreeNode curr = queue.poll();
+                    if (curr.left != null) {
+                        queue.offer(curr.left);
+                        childToParentMap.put(curr.left.val, curr.val);
+                    }
+                    if (curr.right != null) {
+                        queue.offer(curr.right);
+                        childToParentMap.put(curr.right.val, curr.val);
+                    }
+                }
+                if (childToParentMap.containsKey(x) && childToParentMap.containsKey(y) && childToParentMap.get(x) != childToParentMap.get(y)) {
+                    return true;
+                } else if (childToParentMap.containsKey(x) || childToParentMap.containsKey(y)) {
+                    return false;
+                }
+            }
+            return false;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_993Test.java b/src/test/java/com/fishercoder/_993Test.java
@@ -2,42 +2,46 @@
 
 import com.fishercoder.common.classes.TreeNode;
 import com.fishercoder.common.utils.TreeUtils;
-import com.fishercoder.solutions._703;
-import com.fishercoder.solutions._976;
 import com.fishercoder.solutions._993;
-import java.util.Arrays;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
+import java.util.Arrays;
+
 import static junit.framework.Assert.assertEquals;
 
 public class _993Test {
-  private static _993.Solution1 solution1;
-  private static TreeNode root;
-
-  @BeforeClass
-  public static void setUp() {
-    solution1 = new _993.Solution1();
-  }
-
-  @Test
-  public void test1() {
-    root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4));
-    TreeUtils.printBinaryTree(root);
-    assertEquals(false, solution1.isCousins(root, 4, 3));
-  }
-
-  @Test
-  public void test2() {
-    root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4, null, 5));
-    TreeUtils.printBinaryTree(root);
-    assertEquals(true, solution1.isCousins(root, 5, 4));
-  }
-
-  @Test
-  public void test3() {
-    root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4));
-    TreeUtils.printBinaryTree(root);
-    assertEquals(false, solution1.isCousins(root, 2, 3));
-  }
+    private static _993.Solution1 solution1;
+    private static _993.Solution2 solution2;
+    private static TreeNode root;
+
+    @BeforeClass
+    public static void setUp() {
+        solution1 = new _993.Solution1();
+        solution2 = new _993.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4));
+        TreeUtils.printBinaryTree(root);
+        assertEquals(false, solution1.isCousins(root, 4, 3));
+        assertEquals(false, solution2.isCousins(root, 4, 3));
+    }
+
+    @Test
+    public void test2() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4, null, 5));
+        TreeUtils.printBinaryTree(root);
+        assertEquals(true, solution1.isCousins(root, 5, 4));
+        assertEquals(true, solution2.isCousins(root, 5, 4));
+    }
+
+    @Test
+    public void test3() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4));
+        TreeUtils.printBinaryTree(root);
+        assertEquals(false, solution1.isCousins(root, 2, 3));
+        assertEquals(false, solution2.isCousins(root, 2, 3));
+    }
 }
