3

問題の修正版に行き詰まっています(バイナリツリーで距離 k にある2つのノードを見つけます)。

私は 2 つのノード間の距離を定義しようとしていましたが、ツリーの枝に沿ってノード n1 からノード n2 に移動するために必要なノードの最小数であると考えています。

この仮定をうまく進めると、各ノードがルートの左側にあるか右側にあるかを知る必要があると思われる状況にたどり着きました。

ケース 1 : n1 と n2 が異なる側にある場合、ルート (距離はノード n1 の深さに等しい - n1 が左側にあると仮定) に登り、次に右のノード n2 (距離は n2 の深さに等しい) に降ります。 )。したがって、2 つのノード n1 、 n2 間の最大距離は、ルートの異なる側にある場合、それらの深さの合計になります。

ケース 2 : n1 と n2 が同じ側にある場合、ツリー階層で両方​​に共通の祖先を見つけ、ケース 1 と同様に祖先をルートと見なして同じプロセスを繰り返します。最小距離は、ルートからの深さ - 共通の祖先の深さの 2 倍。

さて、これの問題は、ノードのすべてのペアに対してこれを率直に行うことになることです。これ以上の距離にあるノードのペアを知っている場合、ペアをチェックしないように最適化できますが、どうすればよいですか?

残りの解決策を提案してください。

4

1 に答える 1

1

ツリー内の 2 つのリーフ間の最長パス上のノード数として定義されるバイナリ ツリーの直径(ボトムアップ アプローチを参照) と同じ問題。あなたの場合、ノードも見つける必要があります。

于 2012-06-03T06:37:01.167 に答える