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

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)空间。

Answer 2

由于hammar’s answer演示，您的算法是相当低效的，因为许多操作重复。

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

下面是一个（未经测试）实现在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）。