Re：バイナリ検索ツリーと数字が与えられていると、ノードのデータが与えられた番号に追加されたパスを見つける

Question

私はこの問題を見た：Given a binary search tree and a number, find a path whose node's data added to be the given number.。

バイナリ検索ツリーと数字があれば、ルートからリーフまでのパスがあるかどうかを調べ、パス上のすべての数字が指定された数になるようにします。

このスレッドの誰もがこれを行う再帰的な方法を知っているようです。

何か不足していますか？これを再帰的にどのように解決しますか？木全体に力を入れなければならないのですか？

誰かがこれを行う方法の概要（大雑把なアイデア）を与えることはできますか？

Answer 1

再帰的アプローチはf(node, len)のように行われ、左右のノードを通過するときにはf(node->left, len-left)またはf(node->right,len-right)に変更されます。あなたが葉に下ったら、現在のlen==0とすべてが完了しているかどうかをチェックします。

この再帰的なアプローチは、実際にはブルートフォースと同じですが、私がその記事で言ったように、メモアイテクニックを使って速くすることができます。

Answer 2

あなたは予想通りです：ツリーの走査を行います。ここで、子ノードの呼び出しには、呼び出し元の目標値から呼び出し元の値を差し引いた目標値があります。リーフが目標値を持つときに検索が停止します。これはBSTなので、その子のターゲットが現在のノードの値より小さいときはいつでも、右の子を検索することをやめることができます（b/c右のサブツリーのすべてがそれ以下である）。