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