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

Question

我知道类似的问题已经被问过，但我觉得我的解决方案就简单得多了。特别是相对于维基百科。

请证明我错了！

如果你有一个树与具有给定的数据结构中的节点：

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解决。首先，你考虑二叉树，他认为正叉树;但是这可能是一个细节。更重要的是，你考虑搜索树，而考虑的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


}