add 1644

fishercoder1534 · fishercoder1534 · commit e0e9003c3888 · 2021-07-29T17:30:55.000-07:00
diff --git a/README.md b/README.md
@@ -130,6 +130,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1656|[Design an Ordered Stream](https://leetcode.com/problems/design-an-ordered-stream/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1656.java) ||Easy|Array, Design|
 |1652|[Defuse the Bomb](https://leetcode.com/problems/defuse-the-bomb/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1652.java) ||Easy|Array|
 |1646|[Get Maximum in Generated Array](https://leetcode.com/problems/get-maximum-in-generated-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1646.java) ||Easy|Array|
+|1644|[Lowest Common Ancestor of a Binary Tree II](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1644.java) ||Medium|Binary Tree, DFS|
 |1642|[Furthest Building You Can Reach](https://leetcode.com/problems/furthest-building-you-can-reach/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1642.java) ||Medium|Binary Search, Heap|
 |1641|[Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1641.java) |[:tv:](https://youtu.be/gdH4yfgfwiU)|Medium|Math, DP, Backtracking|
 |1640|[Check Array Formation Through Concatenation](https://leetcode.com/problems/check-array-formation-through-concatenation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1640.java) ||Easy|Array, Sort|
diff --git a/src/main/java/com/fishercoder/solutions/_1644.java b/src/main/java/com/fishercoder/solutions/_1644.java
@@ -0,0 +1,49 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+public class _1644 {
+    public static class Solution1 {
+        /**
+         * This is my not so elegant but original solution to get it accepted.
+         */
+        boolean[] exists = new boolean[2];
+
+        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+            exists(p, root, 0);
+            exists(q, root, 1);
+            if (!exists[0] || !exists[1]) {
+                return null;
+            }
+            return dfs(root, p, q);
+        }
+
+        private void exists(TreeNode target, TreeNode root, int index) {
+            if (root == null) {
+                return;
+            }
+            if (target == root) {
+                exists[index] = true;
+                return;
+            }
+            if (!exists[index]) {
+                exists(target, root.left, index);
+            }
+            if (!exists[index]) {
+                exists(target, root.right, index);
+            }
+        }
+
+        private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
+            if (root == null || p == root || q == root) {
+                return root;
+            }
+            TreeNode left = lowestCommonAncestor(root.left, p, q);
+            TreeNode right = lowestCommonAncestor(root.right, p, q);
+            if (left != null && right != null) {
+                return root;
+            }
+            return left != null ? left : right;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1644Test.java b/src/test/java/com/fishercoder/_1644Test.java
@@ -0,0 +1,27 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1644;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1644Test {
+    private static _1644.Solution1 solution1;
+
+    @Test
+    public void test1() {
+        solution1 = new _1644.Solution1();
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4));
+        TreeUtils.printBinaryTree(root);
+        TreeNode p = TreeUtils.constructBinaryTree(Arrays.asList(5, 6, 2, null, null, 7, 4));
+        TreeUtils.printBinaryTree(p);
+        TreeNode q = new TreeNode(10);
+        TreeNode actual = solution1.lowestCommonAncestor(root, p, q);
+        System.out.println("actual: " + actual);
+        assertEquals(null, actual);
+    }
+}
