java - 二分木非再帰バージョンでの最小共通祖先検索 - Java

Question

Java で記述されたソートされたバイナリ ツリーで最小共通祖先を見つける非再帰アルゴリズム バージョンを検索しています。私が見つけたものはすべて、再帰バージョンのみです (stackoverflow や他の Web サイトでも)。

非再帰バージョン (while ループを使用) を書いたり、指示したりできますか? このバージョンが時間の複雑さの点でより効率的かどうかも書いてください?

Answer 1

この長い間忘れられていた質問をたまたま見ました。

木が与えられた場合、次のようなことを意味しますか。

       A
   B       C
 D   E   F   G
H I J K L M N O

commonAncestor(L,G) = C
commonAncestor(H,O) = A
commonAncestor(B,H) = B

そんな感じ？

与える 2 つの方法 (すべて、提供されたノードがツリー内にあると仮定します):

親へのリンクがある場合 (つまり、B から A に戻っている場合)、交差するリンク リストを見つけるのと同様に、解決策は簡単です。

D1深さがと であると仮定して、Node1 と Node2 の深さを見つけますD2。と の差を求めますD1( とD2仮定d)。Node1 と Node2 へのポインターを持っています (p1 と p2 を想定)。より深い深さのノードの場合、親に d 回移動します。この時点でp1、p2祖先の下に同じ深さがあります。ノードに到達するまで、 と 親のp1両方をナビゲートする単純なループを作成するだけです。p2p1 == p2

---

ノードに親リンクがない場合は、ツリーを繰り返しナビゲートできます。

currentNode = root;
while (true) {
    if (currentNode == node1 
            || currentNode == node2 
            || (currentNode > node1) != (currentNode > node2) ) {
        break;  // current node is the common ancestor, as node1 and node2 
                // will go to different sub-tree, or we actually 
                // found node1/2 and the other node is its child
    } else if (currentNode > node1) {
        currentNode = currentNode.left;
    } else { // currentNode < node1/2
        currentNode = currentNode.right;
    }
}

// currentNode will be the answer you want

基本的な考え方は、二分探索木である場合、2 つのノードが両方とも現在のノードよりも大きい/小さい場合、同じ子ツリーに移動します。したがって、共通の祖先は、2 つの値が異なる子に移動するノードです。つまり、一方が現在のノードよりも小さく、もう一方が大きい場合です。