3

以前にも同様の質問があったことは知っていますが、私の解決策ははるかに簡単だと思います。特にウィキペディアと比較すると。

私が間違っていることを証明してください！

指定されたデータ構造を持つノードを持つツリーがある場合:

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 はツリー内のノードの数)。

4

3 に答える 3

5

あなたのアルゴリズムは私には問題ないように見えますが、少なくともこれ以上のものは思いつきませんでした。親ポインターは必要ないことに注意してください。代わりに、ルートからツリーをたどって、キーが 2 つの初期キーの間にある最初のノードを見つけることができます。

ただし、あなたの問題は、Tarjan が解決した問題とは何の関係もありません。まず、あなたは二分木を考えますが、彼は n 分木を考えます。しかし、これはおそらく詳細です。さらに重要なことは、検索ツリーを考慮するのに対し、Tarjan は一般的なツリー (キーの順序付けなし) を考慮することです。キーに応じて、特定のノードがツリー内のどこにある必要があるかを推測できるため、問題ははるかに単純です。

于 2010-11-01T19:18:45.040 に答える
1

いいえ、すみません。しかし、あなたのアルゴリズムは良くありません。次の BST を使用します。

10
  \
   \
   15
  / \
 14 16

あなたのアルゴリズムは、最も低い共通の祖先として 10 を返します。

したがって、たとえば左のノードを取り、その親に移動して順序どおりに実行し、順序どおりの出力に右が含まれているかどうかをチェックするアルゴリズムを作成できます。

于 2013-05-15T22:02:19.543 に答える