ツリー内のすべてのノードの最大距離を直線時間で求めよ

Question

ノードの最大距離をそのノードとツリー内の他のすべてのノードの間の距離の最大値として定義します。 私の問題は、ツリー内のすべてのノードの最大距離を見つけて印刷することです（必ずしもバイナリではない）。基本的には、各ノードについて、私が見ているノードとツリー内の他のノードとの間にあるノードの最大距離をプリントアウトする必要があります。ランタイムはO（n）であると予想されます。

私の最善のアプローチはすべてO（N^2）時間かかるので、この問題をどこで解決するかはわかりません。私は現在、ツリー内の各ノードの最大距離を見つけるために、ツリー内のすべてのノードでBFSを実行しますが、より良いアプローチは、何らかの形の動的プログラミングを使用することです。私は確信していません。

ご協力いただきありがとうございます。

Answer 1

任意のノードをルートとして選択しましょう。今、私たちは根っこの木を持っています。

サブツリー内で一番遠いノードを見つけることは簡単です。それは一番高い葉です（サブツリー内の最も遠いノードのためのサブツリー動的プログラミングが機能します）。

しかし、サブツリーに含まれていない場合はどうなりますか？それは根のために起こることはできませんので、私たちはそれに対する答えを持っています。私たちがその子供に行きたいと仮定しよう。私たちは、これ以外のルートのすべての子孫のサブツリーに最も遠い葉を考慮する必要があります。純粋にすべての子供を反復すると、最悪の場合、n^2時間の複雑さが生じる。しかし、2人の最良の子供を格納することによって、固定された子供以外の最適な子供を見つけることができる。他のノードでも同じことができるので、線形時間で動作します。