有没有更好的方法来查找最近公共祖先？

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是树中节点的数量）。

- theninjagreg

Answer 1

你的算法看起来还不错，至少我想不到更好的方法。请注意，你不需要父节点指针；相反，你可以从根节点开始遍历树，找到第一个键位于两个初始键之间的节点。

然而，你的问题与Tarjan解决的问题无关。首先，你考虑二叉树，而他考虑n元树；但这可能只是一个细节。更重要的是，你考虑搜索树，而Tarjan考虑一般树（键上没有排序）。你的问题要简单得多，因为根据键，你可以猜测某个节点在树中的位置。

- ksson

Answer 2

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


}

- user2450342

Answer 3

不好意思，但是您的算法并不好。 以以下二叉搜索树为例：

10
  \
   \
   15
  /  \
 14  16

您的算法将返回10作为最近公共祖先。

因此，您可以编写一个算法，取左节点，然后转到其父节点，在其上运行中序遍历，并检查右侧是否在中序遍历的输出中。

- tsvi