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

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解决的问题无关.首先,你考虑二元树,他考虑n-ary树; 但这可能是一个细节.更重要的是,你考虑搜索树,而Tarjan考虑一般树(没有按键排序).您的问题要简单得多,因为根据密钥,您可以猜测某个节点必须在树中的位置.