add a solution for 1644

fishercoder1534 · fishercoder1534 · commit ef94e1b91732 · 2021-08-27T16:55:44.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_1644.java b/src/main/java/com/fishercoder/solutions/_1644.java
@@ -46,4 +46,26 @@ private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
             return left != null ? left : right;
         }
     }
+
+    public static class Solution2 {
+        int found = 0;
+
+        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
+            TreeNode lca = lca(root, p, q);
+            return found == 2 ? lca : null;
+        }
+
+        private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
+            if (root == null) {
+                return root;
+            }
+            TreeNode left = lca(root.left, p, q);
+            TreeNode right = lca(root.right, p, q);
+            if (root == p || root == q) {
+                found++;
+                return root;
+            }
+            return left == null ? right : right == null ? left : root;
+        }
+    }
 }
