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

這題跟前兩題不同處是.., 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

space: O(h), same

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

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

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

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