以下是我的算法来找到共同祖先。但我不知道如何计算它的时间复杂性，任何人都可以帮忙吗？

 公共树commonAncestor（树根，树磷，树Q）{
    如果（封面（root.left页）及＆安培;盖（root.left，Q））
        返回commonAncestor（root.left，P，Q）;
    如果（封面（root.right页）及＆安培;盖（root.right，Q））
        返回commonAncestor（root.right，P，Q）;
    返回根;
}
私人布尔盖（树根，树P）{/ *是根PA的孩子呢？ * /
    如果（根== NULL）返回false;
    如果（根== p）的返回true;
    返回盖（root.left，P）||封面（root.right，p）的;
}
 

解决方案

好了，让我们首先确定什么最坏的情况下这个算法是。 封面搜索从左到右树，让您得到最坏情况的行为，如果您正在搜索的节点是最右边的叶子，或者它是不是在子树所有。在这一点上，你会把访问过的所有节点的子树，所以封面是 O（N）的，其中的 N 是节点的树中的数

同样， commonAncestor 展品最坏情况下的行为，当 P 的共同祖先和问：是内心深处的权利在树上。在这种情况下，它会先调用封面两次，得到在两种情况下最糟糕时的行为。然后，它会再次调用本身的右子树，它在平衡树的情况下是大小 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 或①与封面，让我们确定整个路径 P 和①。这需要 O（N）就像盖，我们只是保持更多的信息。现在，遍历parallell这些路径，并停止在那里发散。这始终是 O（N）。

如果你从每个节点到他们的父母，你甚至可以通过生成路径自下而上，给你 O（log n）的为改善这一指针平衡树。

请注意，这是一个时空的权衡，因为当你的code采用 O（1）的空间，该算法采用 0一般（log n）的的空间均衡的树， O（N）的空间。

Following is my algorithm to find first common ancestor. But I don’t know how to calculate it time complexity, can anyone help?

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

Ok, so let's start by identifying what the worst case for this algorithm would be. covers searches the tree from left to right, so you get the worst-case behavior if the node you are searching for is the rightmost leaf, or it is not in the subtree at all. At this point you will have visited all the nodes in the subtree, so covers is O(n), where n is the number of nodes in the tree.

Similarly, commonAncestor exhibits worst-case behavior when the first common ancestor of p and q is deep down to the right in the tree. In this case, it will first call covers twice, getting the worst time behavior in both cases. It will then call itself again on the right subtree, which in the case of a balanced tree is of size n/2.

Assuming the tree is balanced, we can describe the run time by the recurrence relation T(n) = T(n/2) + O(n). Using the master theorem, we get the answer T(n) = O(n) for a balanced tree.

Now, if the tree is not balanced, we might in the worst case only reduce the size of the subtree by 1 for each recursive call, yielding the recurrence T(n) = T(n-1) + O(n). The solution to this recurrence is T(n) = O(n^2).

You can do better than this, though.

For example, instead of simply determining which subtree contains p or q with cover, let's determine the entire path to p and q. This takes O(n) just like cover, we're just keeping more information. Now, traverse those paths in parallell and stop where they diverge. This is always O(n).

If you have pointers from each node to their parent you can even improve on this by generating the paths "bottom-up", giving you O(log n) for a balanced tree.

Note that this is a space-time tradeoff, as while your code takes O(1) space, this algorithm takes O(log n) space for a balanced tree, and O(n) space in general.