代码之家 › 专栏 › 技术社区 › theninjagreg

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

least-common-ancestor binary-search-tree c

theninjagreg · 技术社区 · 14 年前

我知道以前也有人问过类似的问题,但我认为我的解决方法要简单得多。尤其是与 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;
}

3 回复 | 直到 11 年前

ksson 14 年前

你的算法看起来不错,至少我想不出更好的了。注意,您不需要父指针;相反,您可以从根开始向下搜索树,并找到其键位于两个初始键之间的第一个节点。

然而,你的问题与塔扬解决的问题无关。首先,你考虑二叉树,他考虑n叉树,但这可能是一个细节。更重要的是,您考虑的是搜索树,而Tarjan考虑的是一般树(键上没有排序)。您的问题要简单得多,因为根据键的不同,您可以猜测树中的某个节点必须位于何处。

tsvi 11 年前

但你的算法不好。采取以下BST:

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

user2450342 11 年前

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


}

推荐文章

mourinho · Python中按顺序遍历树返回列表

6 年前

Dongho Han · 用C语言中的二叉搜索树查找合计

6 年前

Richard Cooper · 使用递归的C++二叉搜索树

6 年前

Pranshu · 无法删除二进制搜索树中的根节点

6 年前

user2411290 · BST Delete函数不删除目标节点(Java)

7 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

7 年前

Vanshaj · 给定的数字序列是否有唯一的二进制搜索树?

7 年前

M.Hamra · 如何编写递归函数来返回BST中的最小值?

7 年前

Matt · 二进制搜索树遍历方法,以便字符串

7 年前

I.Klein · 递归获取二叉搜索树的高度[闭合]

7 年前