有沒有更好的方法找到最低的共同祖先？

Question

我知道以前有類似的問題，但我認爲我的解決方案要簡單得多。特別是與Wikipedia相比。

請證明我的看法！

如果你有一個包含了給定數據結構的節點樹：

struct node 
{ 
    node * left; 
    node * right; 
    node * parent; 
    int key; 
} 

你可以寫這樣的功能：

node* LCA(node* m, node* n) 
{ 
    // determine which of the nodes is the leftmost 
    node* left = null; 
    node* right = null; 
    if (m->key < n->key) 
    { 
     left = m; 
     right = n; 
    } 
    else 
    { 
     left = n; 
     right = m; 
    } 
    // start at the leftmost of the two nodes, 
    // keep moving up the tree until the parent is greater than the right key 
    while (left->parent && left->parent->key < right->key) 
    { 
     left = left->parent; 
    } 
    return left; 
} 

這段代碼非常簡單，最糟糕的情況是O （n），平均情況下它可能是O（logn），特別是如果樹是平衡的（其中n是樹中節點的數量）。

Answer 1

你的算法對我來說看起來不錯，至少我想不出任何更好的東西。請注意，您不需要父指針;相反，您可以從根開始往下走，找到第一個節點，它的鍵位於兩個初始鍵之間。

但是，你的問題與Tarjan解決的問題無關。首先，你考慮二叉樹，他認爲n-ary樹;但這可能是一個細節。更重要的是，你考慮搜索樹，而Tarjan考慮一般樹（沒有按鍵排序）。你的問題要簡單得多，因爲根據密鑰，你可以猜測樹中某個節點的位置。

Answer 2

不，我很抱歉。 但是你的算法不好。 採取以下BST：

 
10 
    \ 
    \ 
    15 
/\ 
14 16 

找你的算法將返回10作爲最低的共同祖先。

因此，你可以寫算法，採取，比如說，左節點，不是去其父親，並且按順序在其上運行，並且檢查是否正確是的有序

Answer 3

Node* getAncestor(Node* root, Node* node1 , Node* node2) 
{ 
    if(root->val > node1->val && root->val > node2->val) 
     getAncestor(root->left , node1 , node2); 
    //recursive call with left subtree 

    if(root->val < node1->val && root->val < node2->val) 
     getAncestor(root->right , node1 , node2); 
    //recursive call with right subtree 

    return root ; 
    //returning the root node as ancestor 

    //initial call is made with the tree's root node 
    //node1 and node2 are nodes whose ancestor is to be located 


} 

輸出