[解決済み] 任意の二分木における2つのノードの最小公倍数の先祖を見つけるには？

質問

ここでいうバイナリツリーは、必ずしもバイナリサーチツリーであるとは限りません。

という構造にも取れる。

struct node {
    int data;
    struct node *left;
    struct node *right;
};

友人と一緒に考え出した最大限の解決策は、このようなものでした。

検討する この二分木は :

順序トラバーサルは、-8、4、9、2、5、1、6、3、7を生成します。

そして、後順序のトラバーサルは、-8, 9, 4, 5, 2, 6, 7, 3, 1を生成します。

例えば、ノード8と5の共通の先祖を見つけたい場合、順序木探索で8と5の間にあるすべてのノードのリストを作成します（この場合は [4, 9, 2] となります）。したがって、8と5の共通の祖先は2である。

このアルゴリズムの計算量はO(n)だと思います（順次走査と逆順走査はO(n)、残りのステップは配列の単純な反復に過ぎないのでこれもO(n)）．しかし、これが間違っている可能性も高いです :-)

しかし、これは非常に粗雑なアプローチで、場合によっては破綻するかもしれませんね。他に（より最適と思われる）解決策はないのでしょうか？

どのように解決するのですか？

Nick Johnsonの言うとおり、親ポインタがない場合、時間計算量O(n)のアルゴリズムがベストです)。このアルゴリズムの単純な再帰的バージョンについては、以下のコードを参照してください。 Kindingさんの投稿 これはO(n)時間で実行されます。

しかし、もしノードが親ポインタを持っているならば、よりよいアルゴリズムが可能であることに留意してください。問題の両方のノードについて、ルートからノードへのパスを含むリストを構築します。これは、ノードから開始し、親を前に挿入します。

つまり、例の 8 の場合、（ステップを示す）{4}, {2, 4}, {1, 2, 4} が得られます。

もう1つのノードにも同じことをすると、次のようになります（ステップは表示されません）。

ここで、作成した2つのリストを比較して、リストが異なる最初の要素、または、どちらかのリストの最後の要素の、どちらか先にあるものを探します。

このアルゴリズムに必要な時間はO(h)であり、hは木の高さである。最悪の場合、O(h)はO(n)に相当するが、木がバランスしていれば、それはO(log(n))に過ぎない。また、O(h)の空間が必要である。定数空間しか使わない改良版も可能であり、そのコードは CEGRDの投稿

木がどのように構築されたかに関わらず、この操作を木に対して何度も行い、その間に木を変更しないのであれば、O(n) [線形]時間の準備を必要とし、その後ペアを見つけるのに O(1) [一定] 時間だけかかる他のアルゴリズムを使用することが可能です。これらのアルゴリズムに関する参考文献は ウィキペディア . (このリンクを最初に貼ってくれたJasonに感謝します)