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

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叉树；但这可能是一个细节。更重要的是，您考虑的是搜索树，而 Tarjan 考虑的是一般树(不对键进行排序)。您的问题要简单得多，因为根据 key ，您可以猜测某个节点在树中的位置。