tree - 二分木の与えられたノードから最も近い葉ノードを見つける

Question

ルートノードと特定のノードを持つバイナリツリー（必ずしもバイナリ検索ツリーである必要はありません）が与えられた場合、指定されたノードに最も近いリーフノードを見つける方法は??

この問題に対する特定のアルゴリズムまたは既存のアルゴリズムの変更はありますか??

Answer 1

このリンクを確認してください。アイデアは、指定されたツリーを前の順序でトラバースし、配列内の先祖を追跡することです。指定されたキーに到達すると、指定されたキーをルートとするサブツリー内の最も近い葉の距離を評価します。また、すべての祖先を 1 つずつトラバースし、祖先をルートとするサブツリーで最も近い葉の距離を見つけます。すべての距離を比較し、最小値を返します。