大厂面试真题详解:最近公共祖先 II

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

上一篇:算法面试真题详解:硬币排成线


下一篇:大厂面试真题详解:三角形计数