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

Question

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

algorithmbinary-treeleast-common-ancestor

8

以下是我寻找第一个共同祖先的算法。但我不知道如何计算它的时间复杂度，有人可以帮忙吗？

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);
}

- dojoBeginner

2个回答

0

正如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)。

- Gumbo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hammar · Accepted Answer

好的，让我们先确定一下这个算法的最坏情况。 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)。

不过，你可以做得更好。

例如，不要仅使用 cover 确定哪个子树包含 p 或 q，而是确定到 p 和 q 的整个路径。这与 cover 一样需要 O(n) 的时间，我们只是保留了更多的信息。现在，以并行方式遍历这些路径，并在它们分开的地方停止。这总是 O(n)。

如果每个节点都有指向其父节点的指针，您甚至可以通过“自下而上”生成路径来改进此算法，对于平衡树，这将使您获得 O(log n)。

请注意，这是一种时空权衡，因为虽然您的代码占用 O(1) 的空间，但该算法对于平衡树占用 O(log n) 的空间，对于一般情况则占用 O(n) 的空间。