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

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 是树中的节点数。

同样，当p和q的第一个共同祖先位于树的右侧深处时，commonAncestor表现出最坏情况的行为。在这种情况下，它将首先调用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 with cover，不如让我们确定 p 和 q 的整个路径。这需要O(n)就像cover一样，我们只是保留更多信息。现在，并行遍历这些路径，并在它们发岔的地方停止。这总是O(n).

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

请注意，这是一个时空权衡，因为虽然您的代码占用O(1)空间，但此算法占用O(log n)空间用于平衡树，并且通常占用O(n)空间。

Answer 2

正如 hammar 的答案所表明的那样，您的算法效率非常低，因为许多操作都是重复的。

我会做一个不同的方法：如果两个给定节点不在同一子树中（因此使其成为第一个共同祖先），我将确定从根到两个给定节点的路径并比较节点，而不是测试每个潜在的根节点。然后，从根向下的路径上的最后一个公共节点也是第一个公共祖先。

下面是 Java 中的一个（未经测试的）实现：

private List<Tree> pathToNode(Tree root, Tree node) {
    List<Tree> path = new LinkedList<Tree>(), tmp;
    // root is wanted node
    if (root == node) return path;
    // check if left child of root is wanted node
    if (root.left == node) {
        path.add(node);
        path.add(root.left);
        return path;
    }
    // check if right child of root is wanted node
    if (root.right == node) {
        path.add(node);
        path.add(root.right);
        return path;
    }
    // find path to node in left sub-tree
    tmp = pathToNode(root.left, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    // find path to node in right sub-tree
    tmp = pathToNode(root.right, node);
    if (tmp != null && tmp.size() > 1) {
        // path to node found; add result of recursion to current path
        path = tmp;
        path.add(0, node);
        return path;
    }
    return null;
}
public Tree commonAncestor(Tree root, Tree p, Tree q) {
    List<Tree> pathToP = pathToNode(root, p),
               pathToQ = pathToNode(root, q);
    // check whether both paths exist
    if (pathToP == null || pathToQ == null) return null;
    // walk both paths in parallel until the nodes differ
    while (iterP.hasNext() && iterQ.hasNext() && iterP.next() == iterQ.next());
    // return the previous matching node
    return iterP.previous();
}

pathToNode 和 commonAncestor 都在 O（n） 中。