# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/lca/1650.-lca-lowest-common-ancestor-of-a-binary-tree-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.