> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/tree/lca/1650.-lca-lowest-common-ancestor-of-a-binary-tree-iii.md).

# 1650. (LCA) Lowest Common Ancestor of a Binary Tree III

![](/files/-MlL7MjlhOlsUuCCKWb5)

![](/files/-MlL7RMzO7G4BbZaXaEe)

這題跟前兩題不同處是.., node 本身有 parent info, 

而且沒有 root input,  所以要利用 parent 來找

## has parent info, use hashset to stroe parent info

```
because this question gives parent Node

so put p's all parent Nodes into a set<>

then check all q's all parents are in set? if find, it's LCA!
```

time: O(h), worst case is from leaf to root, is tree's height&#x20;

space: O(h), same

因為有 parent, 所以跟之前的概念雷同, 如果用暴力法的概念去想(之前有提到,

LCA 會出現從 p 往上, q 往上, 交會之處

所以可以先把 p 往上的 路徑（parent 路徑)記起來, q 往上的 路徑, 直接去比對, 那找到就是 LCA

```java
class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set = new HashSet<>();
        Node curr = p;
        while (curr != null) {
            set.add(curr);
            curr = curr.parent;
        }
        curr = q;
        while (curr != null) {
            if (set.contains(curr)) {
                return curr;
            }
            curr = curr.parent;
        }
        return null;
    }
}
```