C＃でのリバース幅優先トラバーサル

Question

誰もがC＃？

でリバース幅優先トラバーサルアルゴリズムの準備実装を持っています

でリバース幅優先トラバーサル、私が代わりに共通のノードから始まるツリーを検索するのでは意味、私は下からツリーを検索すると、徐々に共通ノードに収束します。

レッツは、下図を参照してください、これは幅優先トラバーサルの出力です：

私は逆幅優先トラバーサル、9、10、11と12では最初の数のノードになります（これらはすべて、一次あるとして、それらの順序は重要ではありません）を発見しました。 5、6、7及び8第少数のノードが見つかり、そして上のようにしています。 1は、最後のノードを見つけることでしょう。

任意のアイデアやポインタ？

編集：変更「幅優先探索」「幅優先トラバーサル」という質問を明確にすると、

Answer 1

rootNodeから通常のBFSを実行し、depth[i] = linked list of nodes with depth iをしましょう。だからあなたたとえば、あなたが持っているでしょう。

depth[1] = {1}, depth[2] = {2, 3, 4} etc.。あなたは、単純なBFSの検索でこれを構築することができます。次いでdepth[maxDepth]等のものをdepth[maxDepth - 1]内のすべてのノードを、印刷

ノードiの深さは、ルートノードのそのファザーノード+ 1深さの深さに等しい1または0とみなすことができる。

Answer 2

を使用するスタックとキューの組み合わせます。

（私はあなたがすでにやって知っていると推定）キューを使用して「通常の」BFSを行い、そしてあなたがそれらが発生したとして、スタック上のノードをプッシュし続けるます。

BFSで行われると、スタックは逆のBFSの順序が含まれています。