如何在二叉树中找到节点的第一个共同祖先？

Question

以下是我找到第一个共同祖先的算法.但我不知道如何计算它的时间复杂度,任何人都可以帮忙吗？

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    if (covers(root.left, p) && covers(root.left, q))
        return commonAncestor(root.left, p, q);
    if (covers(root.right, p) && covers(root.right, q))
        return commonAncestor(root.right, p, q);
    return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}

Answer 1

好吧,让我们首先确定这种算法的最坏情况.covers从左到右搜索树,因此如果您要搜索的节点是最右边的叶子,或者根本不在子树中,则会出现最坏情况的行为.此时您将访问子树中的所有节点,因此covers是O(n),其中n是树中的节点数.

类似地,commonAncestor当树的第一个共同祖先p并且q在树的右下方时,表现出最坏情况的行为.在这种情况下,它将首先调用covers两次,在两种情况下都会遇到最糟糕的时间行为.然后它将在右侧子树上再次调用自身,在平衡树的情况下,该子树的大小n/2.

假设树是平衡的,我们可以通过递归关系描述运行时间T(n) = T(n/2) + O(n).使用主定理,我们得到T(n) = O(n)了平衡树的答案.

现在,如果树是不均衡的,我们可能会在最坏的情况下,只有通过各1个递归调用减少子树的大小,产生复发T(n) = T(n-1) + O(n).这种复发的解决方案是T(n) = O(n^2).

不过,你可以做得更好.

例如,而不是简单地确定哪个子树包含p或q同cover,让我们确定整个路径p和q.这就O(n)像是cover,我们只是保留更多信息.现在,以平行方式遍历这些路径并停在它们发散的地方.这总是如此O(n).

如果您有从每个节点到其父节点的指针,您甚至可以通过生成"自下而上"的路径来改进这一点,从而为您O(log n)提供平衡的树.

请注意,这是一个时空权衡,因为当您的代码占用O(1)空间时,此算法会O(log n)为平衡树和O(n)空间提供空间.