algorithm - ツリー内のノードのセット間の最長パスを検索します

Question

最近、プログラミングの質問に出くわしました。

ツリーが与えられた場合、非バイナリにすることも、N個のノードを持つ単一のチェーン（または線形）にすることもできます。

入力は、a1、a2....akで示されるKノードのセットになります。それらのKノードの1つから始まり、それらのKノードの1つ（開始ノードとは異なる）で終わる最長の単純なパスを見つけたいと思います。NまたはKに依存する対数アルゴリズムは、必要に応じて実行時間の要件（KlogK、KlogNなど）を満たす必要があります。これは、希望する制限時間内である必要があります。

ありがとうございました

Answer 1

多分あなたはこのアプローチを試すことができます -

1. 任意のノードから DFS を実行して、最も遠いリーフ ノードを見つけます。これをノード X と呼びます。
2. 別の DFS を実行して、X から最も遠いノードを見つけます。
3. 手順 2 で見つけたパスは、ツリー内で最も長いパスです。

これは、バイナリ ツリーだけでなく、すべてのツリーで機能するはずです。