問題は、特定の合計がBSTの任意のパスに存在するかどうかを確認することです。パスがルートからリーフを意味する場合、質問は非常に簡単です。パスが、ルートまたはリーフを含まない可能性があるルートからリーフへのパスの一部を意味する場合、質問は簡単です。ただし、パスはノードの左右両方の子にまたがる可能性があるため、ここでは困難になります。たとえば、与えられた図では、合計132が円で囲まれたパス上に存在します。そのような道の存在をどうやって見つけることができますか？ハッシュを使用してノードの下にすべての可能な合計を格納することは嫌われています！
私は順番に左のサブツリーをトラバースし、逆の順序で右のサブツリーをトラバースすると同時に、マージソートがどのように機能するかを示します。毎回、オウムを近づけるイテレータを移動します。マージソートのようにほとんど。その順序n
あなたは確かにあなたが行くにつれて漸進的に合計して、すべての可能なパスを生成することができます。ツリーがBSTであるという事実により、特定の合計を制限することで時間を節約できる可能性がありますが、それによって漸近的な速度が向上するかどうかはわかりません。問題は、特定のノードの左の子を使用して形成された合計が、右の子を使用して形成された合計よりも必ずしも小さいとは限らないことです。これは、前の合計のパスにさらに多くのノードが含まれる可能性があるためです。次のアルゴリズムは、BSTだけでなく、すべてのツリーで機能します。
可能なすべてのパスを生成するには、パスの最上部のポイントが特別であることに注意してください。パスに両方の子を含めることが許可されているのは、パス内の唯一のポイントです（必須ではありません）。すべてのパスには、一意の最上位ポイントが含まれています。したがって、再帰の外側の層は、すべてのツリーノードにアクセスし、そのノードを最上位ポイントとして持つすべてのパスを生成する必要があります。
// Report whether any path whose topmost node is t sums to target.
// Recurses to examine every node under t.
EnumerateTopmost(Tree t, int target) {
// Get a list of sums for paths containing the left child.
// Include a 0 at the start to account for a "zero-length path" that
// does not contain any children. This will be in increasing order.
a = append(0, EnumerateSums(t.left))
// Do the same for paths containing the right child. This needs to
// be sorted in decreasing order.
b = reverse(append(0, EnumerateSums(t.right)))
// "List match" to detect any pair of sums that works.
// This is a linear-time algorithm that takes two sorted lists --
// one increasing, the other decreasing -- and detects whether there is
// any pair of elements (one from the first list, the other from the
// second) that sum to a given value. Starting at the beginning of
// each list, we compute the current sum, and proceed to strike out any
// elements that we know cannot be part of a satisfying pair.
// If the sum of a[i] and b[j] is too small, then we know that a[i]
// cannot be part of any satisfying pair, since all remaining elements
// from b that it could be added to are at least as small as b[j], so we
// can strike it out (which we do by advancing i by 1). Similarly if
// the sum of a[i] and b[j] is too big, then we know that b[j] cannot
// be part of any satisfying pair, since all remaining elements from a
// that b[j] could be added to are at least as big as a[i], so we can
// strike it out (which we do by advancing j by 1). If we get to the
// end of either list without finding the right sum, there can be
// no satisfying pair.
i = 0
j = 0
while (i < length(a) and j < length(b)) {
if (a[i] + b[j] + t.value < target) {
i = i + 1
} else if (a[i] + b[j] + t.value > target) {
j = j + 1
} else {
print "Found! Topmost node=", t
return
}
}
// Recurse to examine the rest of the tree.
EnumerateTopmost(t.left)
EnumerateTopmost(t.right)
}
// Return a list of all sums that contain t and at most one of its children,
// in increasing order.
EnumerateSums(Tree t) {
If (t == NULL) {
// We have been called with the "child" of a leaf node.
return [] // Empty list
} else {
// Include a 0 in one of the child sum lists to stand for
// "just node t" (arbitrarily picking left here).
// Note that even if t is a leaf node, we still call ourselves on
// its "children" here -- in C/C++, a special "NULL" value represents
// these nonexistent children.
a = append(0, EnumerateSums(t.left))
b = EnumerateSums(t.right)
Add t.value to each element in a
Add t.value to each element in b
// "Ordinary" list merge that simply combines two sorted lists
// to produce a new sorted list, in linear time.
c = ListMerge(a, b)
return c
}
}
上記の擬似コードは、パスの最上位ノードのみを報告します。パス全体は、合計の単純なリストではなくEnumerateSums()ペアのリストを返すことで再構築できます。ここで、は、その合計を生成するために使用されるパスが最初に親ノードから左に移動するかどうかを示すブール値です。(sum, goesLeft)goesLeft
上記の擬似コードは、ノードごとに合計リストを複数回計算します。ツリー内のEnumerateSums(t)上のノードごとに1回呼び出されるだけでなく、それ自体も呼び出されます。各ノードの合計のリストをメモ化して、後続の呼び出しで再計算されないようにすることは可能ですが、実際には漸近解析は改善されません。O（n）の作業のみで、n個の合計のリストを作成できます。単純な再帰であり、これをO（1）に変更しても、全体的な時間計算量は変わりません。これは、への呼び出しによって生成される合計のリスト全体を、とにかく呼び出し元が読み取る必要があり、これにはO（n）時間が必要になるためです。編集： Evgeny Kluevが指摘したように、ttEnumerateSums()EnumerateSums()EnumerateSums()実際にはマージソートのように動作し、ツリーが完全にバランスしている場合はO（nlog n）であり、単一パスの場合はO（n ^ 2）です。したがって、メモ化は実際には漸近的なパフォーマンスの向上をもたらします。
リストのマージを遅延的に実行するイテレータのようなオブジェクトに再配置することで、合計の一時的なリストを取り除くことがEnumerateSums()でき、次の合計を昇順で取得するためにクエリを実行できます。これにEnumerateSumsDown()は、同じことを行うが降順で合計を取得するを作成し、の代わりにこれを使用することも必要になりreverse(append(0, EnumerateSums(t.right)))ます。これを行うと、アルゴリズムのスペースの複雑さがO（n）に下がります。ここで、nはツリー内のノードの数です。これは、各イテレーターオブジェクトが一定のスペース（左右の子イテレーターオブジェクトへのポインターと、最後の合計）、ツリーノードごとに最大1つ存在できます。
最速ではありませんが、単純なアプローチは、2つのネストされた深さ優先探索を使用することです。
通常の深さ優先探索を使用して、開始ノードを取得します。深さ優先探索の2番目の修正バージョンを使用して、このノードから始まるすべてのパスの合計を確認します。
2番目の深さ優先探索は、通常の深さ優先探索とは2つの詳細が異なります。
各DFSの時間計算量はO（N）であるため、合計時間計算量はO（N 2）です。スペース要件はO（N）（両方のDFSスタック用のスペース）です。元のBSTに「親」ポインターが含まれている場合、スペース要件はO（1）です（「親」ポインターを使用すると、スタックなしで任意の方向にツリーを移動できます）。
他のアプローチは、j_random_hackerとrobert kingによるアイデアに基づいています（合計のリストを維持し、それらを照合してから、それらをマージします）。ツリーをボトムアップ方式で処理します（葉から開始）。
DFSを使用して、いくつかのリーフノードを見つけます。次に戻って、最後のブランチノード、つまりこのリーフノードの祖父母を見つけます。これにより、ブランチノードとリーフノードの間にチェーンが作成されます。このチェーンを処理します。
match1(chain)
sum_list = sum(chain)
match1(chain):
i = j = sum = 0
loop:
while (sum += chain[i]) < target:
++i
while (sum -= chain[j]) > target:
++j
if sum == target:
success!
sum(chain):
result = [0]
sum = 0
i = chain.length - 1
loop:
sum += chain[i]
--i
result.append(sum)
return result
DFSを続行し、他のリーフチェーンを検索します。同じノードからの2つのチェーンが見つかった場合、おそらく別のチェーンが前にあります（図の赤と緑のチェーン、青のチェーンが前にあります）。これらのチェーンを処理します。
match2(parent, sum_list1, sum_list2)
sum_list3 = merge1(parent, sum_list1, sum_list2)
if !chain3.empty:
match1(chain3)
match3(sum_list3, chain3)
sum_list4 = merge2(sum_list3, chain3)
match2(parent, sum_list1, sum_list2):
i = 0
j = chain2.length - 1
sum = target - parent.value
loop:
while sum < sum_list1[i] + sum_list2[j]:
++i
while sum > sum_list1[i] + sum_list2[j]:
--j
if sum == sum_list1[i] + sum_list2[j]:
success!
merge1(parent, sum_list1, sum_list2):
result = [0, parent.value]
i = j = 1
loop:
if sum_list1[i] < sum_list2[j]:
result.append(parent.value + sum_list1[i])
++i
else:
result.append(parent.value + sum_list2[j])
++j
return result
match3(sum_list3, chain3):
i = sum = 0
j = sum_list3.length - 1
loop:
sum += chain3[i++]
while sum_list3[j] + sum > target:
--j
if sum_list3[j] + sum == target:
success!
merge2(sum_list3, chain3):
result = [0]
sum = 0
i = chain3.length - 1
loop:
sum += chain3[i--]
result.append(sum)
result.append(sum_list3[1...] + sum)
合計の2つのリスト、またはチェーンと合計のリストが同じノードの子孫である場合は常に同じことを行います。このプロセスは、ルートノードに属する合計の単一のリストが残るまで続けることができます。
複雑さの制限はありますか？あなたが述べたように：「パスが根から葉を意味する場合は簡単、またはパスが根または葉を含まない可能性がある根から葉へのパスの一部を意味する場合は簡単」。毎回ルートを別のノードに設定し、検索をn回実行することで、このステートメントの問題を減らすことができます。それは簡単なアプローチであり、最適かどうかはわかりません。
編集：ツリーが単方向の場合、この種の何かが機能する可能性があります（擬似コード）：
findSum(tree, sum)
if(isLeaf(tree))
return (sum == tree->data)
for (i = 0 to sum)
isfound |= findSum(leftSubStree, i) && findSum(rightSubTree, sum-i)
return isfound;
ここではおそらく多くの間違いがありますが、うまくいけば、それはアイデアを明確にします。