以下は面接の質問です。
各ノードに値が含まれるバイナリツリー（必ずしもBSTである必要はありません）が与えられます。合計がその値になるすべてのパスを出力するアルゴリズムを設計します。ツリー内の任意のパスにすることができることに注意してください。ルートから開始する必要はありません。
ルートで始まるツリー内のすべてのパスが指定された合計を持っていることを見つけることはできますが、ルートで始まらないパスについてはそうすることができません。
ええと、これは木であり、グラフではありません。したがって、次のようなことができます。
擬似コード：
global ResultList
function ProcessNode(CurrentNode, CurrentSum)
CurrentSum+=CurrentNode->Value
if (CurrentSum==SumYouAreLookingFor) AddNodeTo ResultList
for all Children of CurrentNode
ProcessNode(Child,CurrentSum)
さて、これはあなたにルートから始まるパスを与えます。ただし、小さな変更を加えることができます。
for all Children of CurrentNode
ProcessNode(Child,CurrentSum)
ProcessNode(Child,0)
少し考えてみる必要があるかもしれませんが（私は他のことに忙しいです）、これは基本的にツリー内のすべてのノードをルートとする同じアルゴリズムを実行する必要があります
編集：これは実際には「エンドノード」のみを提供します。ただし、これはツリーであるため、これらのエンドノードから開始して、必要な合計が得られるまで上に戻ることができます。
編集2：そしてもちろん、すべての値が正の場合、現在の合計が必要な合計以上であれば、降下を中止できます
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加