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

概述我之前已经问过类似的问题,但我认为我的解决方案要简单得多.特别是与 Wikipedia相比. 请证明我错了！ 如果您的树具有具有给定数据结构的节点： struct node{ node * left; node * right; node * parent; int key;} 你可以写一个这样的函数： node* LCA(node* m, node* n){ 我之前已经问过类似的问题,但我认为我的解决方案要简单得多.特别是与 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是树中的节点数).

解决方法 你的算法看起来没问题,至少我想不出更好的东西.请注意,您不需要父指针;相反,您可以从根目录开始沿着树向下,找到第一个节点,其键位于两个初始键之间.

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

总结

以上是内存溢出为你收集整理的有没有更好的方法来找到最低的共同祖先？全部内容，希望文章能够帮你解决有没有更好的方法来找到最低的共同祖先？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。