给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
每个节点除了左右儿子指针以外，还包含一个父亲指针parent，指向自己的父亲。
在线评测地址：领扣题库官网
样例 1:
输入：{4,3,7,#,#,5,6},3,5
输出：4
解释：
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4样例 2:
输入：{4,3,7,#,#,5,6},5,6
输出：7
解释：
4
/ \
3 7
/ \
5 6
LCA(5, 6) = 7解题思路
- 这道题与88. 最近公共祖先相似，不同的是该题的节点有父指针，所以我们应该充分利用这个信息。我们可以用hashset来解这道题。
算法流程 - 建立集合parentSet，用于存储A的祖先节点。
- 首先，从A向上遍历到root，将路径中的节点都存储到parentSet中。
- 然后，从B向上遍历，判断经过的每个节点是否同时也在parentSet中，第一个出现在parentSet中的点即为A和B的最近公共祖先。
复杂度分析
- 时间复杂度：O(k)，k为树的高度。最差情况下，A是叶节点，从A遍历到root需要O(k)的时间。平均情况下时间复杂度也为O(k)。
- 空间复杂度：O(k)，k为树的高度。最差情况下，A是叶节点，集合中需要存储从A到root的所有节点。平均情况下空间复杂度也为O(k)。
public class Solution {
/*
* @param root: The root of the tree
* @param A: node in the tree
* @param B: node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
ParentTreeNode A,
ParentTreeNode B) {
Set parentSet = new HashSet<>();
// 把A的祖先节点都加入到哈希表中
ParentTreeNode curr = A;
while (curr != null) {
parentSet.add(curr);
curr = curr.parent;
}
// 遍历B的祖先节点，第一个在哈希表中出现的即为答案
curr = B;
while (curr != null) {
if (parentSet.contains(curr)) {
return curr;
}
curr = curr.parent;
}
return null;
}
}更多题解参考：九章官网solution
