バイナリ検索ツリーと番号が与えられた場合、ルートからリーフまでのパスがあるかどうかを調べ、パス上のすべての数字が指定された数になるようにします。バイナリ検索ツリーと数字が与えられた場合、そのノードのデータが与えられた番号に追加されたパスを見つけます。
私は再帰的にそれを行う方法を知っています。しかし、私は反復的な解決策を好む。
あるルートが重複する可能性があるため、毎回ルートからリーフまで繰り返すと、重複が発生します。
ツリーがバイナリ検索ではない場合はどうなりますか？
おかげ
あなたが再帰的に何かできること、あなたも反復して行うことができます。しかし、あなたは再帰的なソリューションでパフォーマンスの問題を抱えているわけではありません。反復的にしようとすると、コード化/読み込みが困難になる可能性は高くなります。
しかし、あなたが主張するならば、スタックを使って再帰的解を反復的解に変換することができます。再帰呼び出しを行うたびに、現在の関数呼び出しの状態変数をスタックにプッシュします。呼び出しが完了したら、変数をポップオフします。
ツリーが平衡していない場合、再帰的にスタックオーバーフローが発生する可能性があります。したがって、反復解が好ましい。しかし、私はあなたのアルゴリズムを理解できません。あなたは疑似コードでそれを言いたいですか？ありがとう – user1002288
基本的に、この問題は、重複するパスを避けるために、ツリー上の動的プログラミングを使用して解決できます。
基本的な考え方は、各リーフから指定されたノードへの可能な長さをテーブルf[node]で追跡することです。これを2次元のブール値配列に実装すると、のようになり、リーフからlenに等しい長さのnodeまでのパスがあるかどうかを示します。ブール値配列を使用する代わりにvector<int>を使用して、それぞれの値をf[node]に格納することもできます。どんなにあなたが使用して表現の種類、あなたは異なるf間で計算する方法これは、バイナリツリーの場合ではありませんが、非バイナリにそれを拡張することは本当に簡単です
f[node] is the union of f[node->left] + len_left[node] and f[node->right] + len_right[node].
の形で、簡単です3つのケース。
不明な点がある場合は、お気軽にコメントしてください。 BSTの場合
：あなたは何度も何度も同じパスを計算したくない場合はderekhhが示唆するように
Node current,final = (initialize)
List nodesInPath;
nodesInPath.add(current);
while(current != final) {
List childrenNodes = current.children;
if(noChildren) noSolution;
if(current < final) {
//choose right child if there is one, otherwise no solution
current = children[right];
} else if(current > final){
//choose left child if there is one, otherwise no solution
current = children[left];
}
nodesInPath.add(current);
}
check sum in the nodesInPath
しかし、非BSTのためにあなたが動的計画法を用いて溶液を適用する必要があります。私は、ある処理されたノードとルートノードの間に合計の長さを格納することができると思います。それらを展開するときの距離を計算します。次に、Breadth-first searchを適用して、同じパスを再び横切らず、以前に計算した合計距離を使用します。アルゴリズムは私の心に来る少し複雑ですが、申し訳ありませんが、それを書くのに十分な時間がありません。
数字が=> 0ですか？ –
再帰的に行うにはいくつかの方法があります。あなたはどちらを使っていますか？あなたは「すべての数字」と言っていますが、あなたはこれらの数字がどこにあるのか、エッジにあるのか、ノードにあるのかは言っていません。 – dasblinkenlight