パスを満た​​さず、k 以上のノードを削除する C++ プログラム

この問題には、ルート ノードからリーフ ノードまでのパスが完全に定義されているバイナリ ツリーがあります。ルート ノードからリーフ ノードまでのすべてのノードの合計は、定数値 k 以上である必要があります。したがって、ツリー内の残りのパスが k より大きくなるように、パス内の合計が k より小さいノードをすべて削除する必要があります。ここで覚えておくべき重要なことは、ノードは多くのパスの一部である可能性があるため、そのようなノードは、そのノードにつながるすべてのパスの合計が k 未満の場合にのみ削除されるということです。

ルート ノードからリーフ ノードまでの合計を計算できます。ノードへの再帰呼び出しが完了して制御が戻ると、左右のパスの合計が k

150 K と次のようなツリーがあるとします -

リーリー

パス root->left->left の合計が 10 20 5、つまり 25 で 150 未満であることがわかった場合は、それを枝刈りして 5 を削除する必要があります。その後、10→30→40と評価してみましょう。 150未満なので40を削除します。

ここで、別のパス 10->20->35->50 が表示されます。115 の合計は 150 未満なので、50 を削除します。残りのパスは

です。 リーリー

すべてのパスの合計は 150 を超えているため、これ以上プルーニングする必要はありません。

＃＃＃例＃＃＃

以下は、どのパスにも存在せず、合計が任意の定数値 k -

以上であるノードを削除する方法を示す C プログラムです。 リーリー ＃＃＃出力＃＃＃ リーリー

完全に剪定された木 -

リーリー ＃＃＃結論は＃＃＃

ご覧のとおり、最初の観察の後、再帰関数が各呼び出しから返されるときにそのノードの合計を計算することで、DFS を適用してノードを削除できます。全体として、これは観察と方法論に関する単純な問題です。

以上がパスを満た​​さず、k 以上のノードを削除する C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。