根から葉への最短経路

Question

BST (二分探索ツリー) でルートからリーフへの最短パスを見つけるための、できれば再帰を使用する最も簡単な方法は何ですか。Java を推奨しますが、擬似コードは問題ありません。

ありがとう！

Answer 1

概要：

使う 幅優先検索 (BFS) とは対照的に 深さ優先検索 (DFS). 。子のない最初のノードを見つけます。

DFS を使用すると、一部の入力ツリーで幸運に恵まれる可能性があります (ただし、幸運だったのかどうかを知る方法はないため、ツリー全体を検索する必要があります)。しかし、BFS 手法を使用するとはるかに高速で、すべてを触らなくても解決策を見つけることができます。ノード。

ルートからリーフへのパスを見つけるには、親参照を使用して、最初に見つかった子のないノードをルートまでたどることができます。各ノードに親参照が保存されていない場合は、下へ再帰しながら親ノードを追跡できます。リストが逆の順序である場合は、すべてをスタックにプッシュしてからポップオフすることができます。

疑似コード:

問題は非常に単純です。最小の長さを見つけるための疑似コードは次のとおりです。

1. ルートノードをキューに入れます。

キューが空ではなく、結果が見つからない間に繰り返します。

2. キューの先頭からノードを取得し、そのノードに子がないかどうかを確認します。子供がいない場合、あなたは終わったことがあります。あなたは最短の道を見つけました。
3. それ以外の場合は、すべての子 (左、右) をキューにプッシュします。

すべての最短パスを見つける:

すべての最短パスを見つけるには、キュー内のノードとともにノードの深さを保存できます。次に、同じ深さのキュー内のすべてのノードに対してアルゴリズムを続行します。

代替：

代わりに DFS を使用することにした場合は、ツリー全体を検索して最短パスを見つける必要があります。ただし、これは、これまでの最短の値を保持し、新しい最短が見つかるまで、またはこれまでの最短に到達するまで、将来のノードの深さをチェックするだけで最適化できます。ただし、BFS ははるかに優れたソリューションです。

Answer 2

これは C++ ですが、非常にシンプルなので簡単に変換できます。ツリーの深さを最大にするには、min を max に変更するだけです。

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

これが何をしているのか説明すると、リーフ ノードからカウントし (リーフを見つけると 0 を返します)、ルートまでカウントアップします。これをツリーの左側と右側で実行し、最小値を取ると、最短パスが得られます。

Answer 3

幅優先検索は、訪問する頂点の数という点でまさに最適です。最も近い葉があることを証明するには、幅優先検索で訪問する頂点をすべて訪問する必要があります。

ただし、再帰を使用する義務がある場合、Mike Thompson のアプローチは次のとおりです。 ほとんど これは、使用するのに適したものであり、もう少し簡単です。

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple(TreeNode root){

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}