给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先 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;     } } 

更多题解参考

大佬有話說 (0)