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

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 ，我们只是保留更多信息。现在，平行穿过这些路径并在它们 fork 的地方停下来。这始终是 O(n) .

如果你有从每个节点到它们父节点的指针，你甚至可以通过生成“自下而上”的路径来改进这一点，给你 O(log n)对于平衡树。

请注意，这是时空权衡，因为您的代码需要 O(1)空间，这个算法需要O(log n)平衡树的空间，以及O(n)一般空间。