add 1490

fishercoder1534 · fishercoder1534 · commit 7abdc6e83043 · 2020-11-22T11:01:13.000-08:00
diff --git a/README.md b/README.md
@@ -69,6 +69,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1493|[Longest Subarray of 1's After Deleting One Element](https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1493.java) |[:tv:](https://youtu.be/nKhteIRZ2Ok) |Medium|Array|
 |1492|[The kth Factor of n](https://leetcode.com/problems/the-kth-factor-of-n/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1492.java) | |Medium|Math|
 |1491|[Average Salary Excluding the Minimum and Maximum Salary](https://leetcode.com/problems/average-salary-excluding-the-minimum-and-maximum-salary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1491.java) | |Easy|Array, Sort|
+|1490|[Clone N-ary Tree](https://leetcode.com/problems/clone-n-ary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1490.java) | |Medium|HashTable, Tree, DFS, BFS|
 |1487|[Making File Names Unique](https://leetcode.com/problems/making-file-names-unique/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1487.java) | |Medium|HashTable, String|
 |1486|[XOR Operation in an Array](https://leetcode.com/problems/xor-operation-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1486.java) | |Medium|Array, Bit Manipulation|
 |1481|[Least Number of Unique Integers after K Removals](https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1481.java) | |Medium|Array, Sort|
diff --git a/src/main/java/com/fishercoder/common/classes/Node.java b/src/main/java/com/fishercoder/common/classes/Node.java
@@ -2,22 +2,24 @@
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Objects;
 
 public class Node {
     public int val;
     public List<Node> children;
 
     public Node() {
+        this.children = new ArrayList<>();
     }
 
-    public Node(int val, List<Node> children) {
+    public Node(int val) {
         this.val = val;
-        this.children = children;
+        this.children = new ArrayList<>();
     }
 
-    public Node(int val) {
+    public Node(int val, List<Node> children) {
         this.val = val;
-        this.children = new ArrayList<>();
+        this.children = children;
     }
 
     //todo: implement this method
@@ -28,4 +30,21 @@ public Node(int val) {
     public static Node createNaryTree(List<Integer> preorderValues) {
         return null;
     }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o == null || getClass() != o.getClass()) {
+            return false;
+        }
+        Node node = (Node) o;
+        return val == node.val && Objects.equals(children, node.children);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(val, children);
+    }
 }
diff --git a/src/main/java/com/fishercoder/solutions/_1490.java b/src/main/java/com/fishercoder/solutions/_1490.java
@@ -0,0 +1,34 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.Node;
+
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+
+public class _1490 {
+    public static class Solution1 {
+        public Node cloneTree(Node root) {
+            if (root == null) {
+                return root;
+            }
+            Map<Node, Node> map = new HashMap<>();
+            map.put(root, new Node(root.val));
+            Queue<Node> queue = new LinkedList<>();
+            queue.offer(root);
+            while (!queue.isEmpty()) {
+                Node curr = queue.poll();
+                for (Node child : curr.children) {
+                    Node childCopy = new Node(child.val);
+                    if (!map.containsKey(child)) {
+                        map.put(child, childCopy);
+                        queue.offer(child);
+                    }
+                    map.get(curr).children.add(childCopy);
+                }
+            }
+            return map.get(root);
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1490Test.java b/src/test/java/com/fishercoder/_1490Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.Node;
+import com.fishercoder.solutions._1490;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1490Test {
+    private static _1490.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1490.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        Node root = new Node(8);
+        Node child = new Node(1);
+        root.children.add(child);
+        Node leftGrandChild = new Node(8);
+        Node rightGrandChild = new Node(5);
+        child.children.add(leftGrandChild);
+        child.children.add(rightGrandChild);
+        assertEquals(root, solution1.cloneTree(root));
+    }
+
+}
