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

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 


} 

输出