13

BST（二分探索木）でルートからリーフへの最短パスを見つけるための最も簡単な方法は、できれば再帰を使用することです。Javaが好まれ、擬似コードは大丈夫です。

ありがとう！

4

5 に答える 5

16

概要：

深さ優先検索 (DFS)ではなく、幅優先検索 (BFS)を使用します。子のない最初のノードを見つけます。

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

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

擬似コード:

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

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

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

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

すべての最短経路を見つける:

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

別：

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

于 2008-09-22T01:12:44.577 に答える
2

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

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

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

于 2008-09-22T01:15:34.367 に答える
0

static int findCheapestPathSimple(TreeNode ルート){

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

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

}

于 2017-01-06T10:36:35.163 に答える
0

幅優先探索は、訪れた頂点の数に関して正確に最適です。最も近い葉があることを証明するためだけに、幅優先検索でアクセスするすべての頂点にアクセスする必要があります。

ただし、再帰を使用する義務がある場合は、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
于 2008-09-22T02:24:09.100 に答える