如何查找二叉樹中節點的第一個共同祖先？

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）。