add 1650

fishercoder1534 · fishercoder1534 · commit 33e668eaf82d · 2021-08-27T17:07:25.000-07:00
diff --git a/README.md b/README.md
@@ -138,6 +138,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1657|[Determine if Two Strings Are Close](https://leetcode.com/problems/determine-if-two-strings-are-close/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1657.java) |[:tv:](https://youtu.be/-jXQK-UeChU)|Medium|Greedy|
 |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|
+|1650|[Lowest Common Ancestor of a Binary Tree III](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1650.java) ||Medium|HashTable, Binary Tree, Tree|
 |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|
diff --git a/src/main/java/com/fishercoder/solutions/_1650.java b/src/main/java/com/fishercoder/solutions/_1650.java
@@ -0,0 +1,45 @@
+package com.fishercoder.solutions;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class _1650 {
+    class Node {
+        public int val;
+        public Node parent;
+        public Node left;
+        public Node right;
+
+        public Node(int val) {
+            this.val = val;
+        }
+    }
+
+    public static class Solution1 {
+        public Node lowestCommonAncestor(Node p, Node q) {
+            Node a = p, b = q;
+            while (a != b) {
+                a = a == null ? p : a.parent;
+                b = b == null ? q : b.parent;
+            }
+            return a;
+        }
+    }
+
+    public static class Solution2 {
+        public Node lowestCommonAncestor(Node p, Node q) {
+            Set<Node> set = new HashSet<>();
+            while (p != null) {
+                set.add(p);
+                p = p.parent;
+            }
+            while (q != null) {
+                if (set.contains(q)) {
+                    return q;
+                }
+                q = q.parent;
+            }
+            return null;
+        }
+    }
+}
