add 1379

fishercoder1534 · fishercoder1534 · commit 0fdc39d97f99 · 2020-03-14T14:29:12.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1379|[Find a Corresponding Node of a Binary Tree in a Clone of That Tree](https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1379.java) | |Medium|Tree|
 |1377|[Frog Position After T Seconds](https://leetcode.com/problems/frog-position-after-t-seconds/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1377.java) | |Hard|DFS, BFS|
 |1376|[Time Needed to Inform All Employees](https://leetcode.com/problems/time-needed-to-inform-all-employees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1376.java) | |Medium|DFS|
 |1375|[Bulb Switcher III](https://leetcode.com/problems/bulb-switcher-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1375.java) | |Medium|Array|
diff --git a/src/main/java/com/fishercoder/solutions/_1379.java b/src/main/java/com/fishercoder/solutions/_1379.java
@@ -0,0 +1,57 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+/**
+ * 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
+ *
+ * Given two binary trees original and cloned and given a reference to a node target in the original tree.
+ * The cloned tree is a copy of the original tree.
+ * Return a reference to the same node in the cloned tree.
+ * Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.
+ *
+ * Follow up: Solve the problem if repeated values on the tree are allowed.
+ *
+ * Example 1:
+ * Input: tree = [7,4,3,null,null,6,19], target = 3
+ * Output: 3
+ * Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.
+ *
+ * Example 2:
+ * Input: tree = [7], target =  7
+ * Output: 7
+ *
+ * Example 3:
+ * Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
+ * Output: 4
+ *
+ * Example 4:
+ * Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
+ * Output: 5
+ *
+ * Example 5:
+ * Input: tree = [1,2,null,3], target = 2
+ * Output: 2
+ *
+ * Constraints:
+ * The number of nodes in the tree is in the range [1, 10^4].
+ * The values of the nodes of the tree are unique.
+ * target node is a node from the original tree and is not null.
+ * */
+public class _1379 {
+    public static class Solution1 {
+        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
+            if (original == null) {
+                return null;
+            }
+            if (original.val == target.val) {
+                return cloned;
+            }
+            TreeNode left = getTargetCopy(original.left, cloned.left, target);
+            if (left != null && left.val == target.val) {
+                return left;
+            }
+            return getTargetCopy(original.right, cloned.right, target);
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1379Test.java b/src/test/java/com/fishercoder/_1379Test.java
@@ -0,0 +1,62 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1379;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+public class _1379Test {
+    private static _1379.Solution1 solution1;
+    private static TreeNode original;
+    private static TreeNode cloned;
+    private static TreeNode target;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1379.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        original = TreeUtils.constructBinaryTree(Arrays.asList(7, 4, 3, null, null, 6, 19));
+        cloned = TreeUtils.constructBinaryTree(Arrays.asList(7, 4, 3, null, null, 6, 19));
+        target = TreeUtils.constructBinaryTree(Arrays.asList(3, 6, 19));
+        TreeUtils.printBinaryTree(solution1.getTargetCopy(original, cloned, target));
+    }
+
+    @Test
+    public void test2() {
+        original = TreeUtils.constructBinaryTree(Arrays.asList(7));
+        cloned = TreeUtils.constructBinaryTree(Arrays.asList(7));
+        target = TreeUtils.constructBinaryTree(Arrays.asList(7));
+        TreeUtils.printBinaryTree(solution1.getTargetCopy(original, cloned, target));
+    }
+
+    @Test
+    public void test3() {
+        original = TreeUtils.constructBinaryTree(Arrays.asList(8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1));
+        cloned = TreeUtils.constructBinaryTree(Arrays.asList(8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1));
+        target = TreeUtils.constructBinaryTree(Arrays.asList(4, null, 3, null, 2, null, 1));
+        TreeUtils.printBinaryTree(solution1.getTargetCopy(original, cloned, target));
+    }
+
+    @Test
+    public void test4() {
+        original = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
+        cloned = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
+        target = TreeUtils.constructBinaryTree(Arrays.asList(5, 10));
+        TreeUtils.printBinaryTree(solution1.getTargetCopy(original, cloned, target));
+    }
+
+    @Test
+    public void test5() {
+        original = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, null, 3));
+        cloned = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, null, 3));
+        target = TreeUtils.constructBinaryTree(Arrays.asList(2, 3));
+        TreeUtils.printBinaryTree(solution1.getTargetCopy(original, cloned, target));
+    }
+
+}
