最も低い共通の祖先を見つけるより良い方法はありますか？

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

あなたのアルゴリズムは私には大丈夫に見えます、少なくとも私はもっと良いことを考えることができませんでした。親ポインターは必要ないことに注意してください。代わりに、ルートから始めてツリーを下りて、2つの初期キーの間にキーが横たわる最初のノードを見つけることができます。

しかし、あなたの問題は、Tarjanが解決したものとは何の関係もありません。まず第一に、あなたはバイナリツリーを検討し、彼はn-aryツリーを考慮します。しかし、これはおそらく詳細です。さらに重要なことに、Tarjanは一般的な木を検討している一方で、ツリーを検索することを検討します（キーには注文はありません）。あなたの問題ははるかに簡単です。なぜなら、キーによっては、特定のノードがツリーのどこにあるかを推測できるからです。

Answer 2

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

10
  \
   \
   15
  /  \
 14  16

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

したがって、たとえば、左ノードを撮影し、その親に移動してその上で順番を実行し、その右が順序の出力にあるかどうかを確認するアルゴリズムを記述することができます。

Answer 3

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


}