add 1485

fishercoder1534 · fishercoder1534 · commit 16f168e0f2ad · 2020-12-05T11:37:59.000-08:00
diff --git a/README.md b/README.md
@@ -78,6 +78,7 @@ _If you like this project, please leave me a star._ &#9733;
 |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|
+|1485|[Clone Binary Tree With Random Pointer](https://leetcode.com/problems/clone-binary-tree-with-random-pointer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1485.java) | |Medium|HashTable, Tree, DFS, BFS|
 |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|
 |1480|[Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1480.java), [C++](../master/cpp/_1480.cpp)| |Easy|Array|
 |1476|[Subrectangle Queries](https://leetcode.com/problems/subrectangle-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1476.java) | |Medium|Array|
diff --git a/src/main/java/com/fishercoder/solutions/_1485.java b/src/main/java/com/fishercoder/solutions/_1485.java
@@ -0,0 +1,107 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class _1485 {
+    public static class Solution1 {
+        public NodeCopy copyRandomBinaryTree(Node root) {
+            if (root == null) {
+                return null;
+            }
+            Map<Node, NodeCopy> map = new HashMap<>();
+            map.put(root, new NodeCopy(root.val));
+            dfs(root, map);
+            dfsAgain(root, map);
+            return map.get(root);
+        }
+
+        private void dfsAgain(Node root, Map<Node, NodeCopy> map) {
+            if (root == null) {
+                return;
+            }
+            NodeCopy copy = map.get(root);
+            if (root.left != null) {
+                copy.left = map.get(root.left);
+            }
+            if (root.right != null) {
+                copy.right = map.get(root.right);
+            }
+            if (root.random != null) {
+                copy.random = map.get(root.random);
+            }
+            map.put(root, copy);
+            dfsAgain(root.left, map);
+            dfsAgain(root.right, map);
+        }
+
+        private void dfs(Node root, Map<Node, NodeCopy> map) {
+            if (root == null) {
+                return;
+            }
+            NodeCopy copy = map.getOrDefault(root, new NodeCopy(root.val));
+            if (root.left != null) {
+                copy.left = new NodeCopy(root.left.val);
+            }
+            if (root.right != null) {
+                copy.right = new NodeCopy(root.right.val);
+            }
+            if (root.random != null) {
+                copy.random = new NodeCopy(root.random.val);
+            }
+            map.put(root, copy);
+            dfs(root.left, map);
+            dfs(root.right, map);
+        }
+    }
+
+    public static class Node {
+        int val;
+        public Node left;
+        public Node right;
+        public Node random;
+
+        public Node() {
+        }
+
+        ;
+
+        public Node(int val) {
+            this.val = val;
+        }
+
+        ;
+
+        public Node(int val, Node left, Node right, Node random) {
+            this.val = val;
+            this.left = left;
+            this.right = right;
+            this.random = random;
+        }
+    }
+
+    public static class NodeCopy {
+        int val;
+        public NodeCopy left;
+        public NodeCopy right;
+        public NodeCopy random;
+
+        public NodeCopy() {
+        }
+
+        ;
+
+        public NodeCopy(int val) {
+            this.val = val;
+        }
+
+        ;
+
+        public NodeCopy(int val, NodeCopy left, NodeCopy right, NodeCopy random) {
+            this.val = val;
+            this.left = left;
+            this.right = right;
+            this.random = random;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1485Test.java b/src/test/java/com/fishercoder/_1485Test.java
@@ -0,0 +1,29 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1485;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+public class _1485Test {
+
+    private static _1485.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1485.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        _1485.Node root = new _1485.Node(1);
+        _1485.Node node1 = new _1485.Node(4);
+        _1485.Node node2 = new _1485.Node(7);
+        root.right = node1;
+        node1.left = node2;
+        node1.random = node2;
+        node2.random = root;
+        _1485.NodeCopy actual = solution1.copyRandomBinaryTree(root);
+        System.out.println("Finished.");
+    }
+
+}
