Lowest Common Ancestor of a Binary Tree III

求LCA. 这次有parent node.

因为有parent, 所以思考后, 可以看出, p和q的欧拉路径必有重合地方. 用Set查重.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

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