sum> = k - 任意の経路にないバイナリ3のすべてのノードを削除する - アルゴリズム、バイナリツリー

与えられた答えを理解できない ここに 誰かが理解するのを助けてくれますか？

私のAlgo：

各パスの総和を再帰的に求める。 sum> = kの場合は、パス内のすべてのノードをハッシュセット 最後にツリーを走査し、ハッシュセットにないノードを削除します。

私はかなり確信しています、ここには多くの改善の余地があります。

回答：

あなたはツリーを持っており、あなたはこれを再帰的に解析しています：

go_node(Node node){
go_node(node.left);
go_node(node.right);
}

あなたの例では、任意のサブツリーを削除したいその値は与えられた数よりも小さい。解決策は簡単ですが、私たちは単純な機能を少し変えて問題を解決します。私は、このコードをできるだけシンプルにするために "K"をグローバル変数にします。ただし、go_nodeメソッドでも解析できます。

int go_node(Node node, int value){
this.total_value = value;
total_value += go_node(node.left, value);
if (node.left.total_value < K){
node.left = null;
}
total_value += go_node(node.right, value);
if (node.right.total_value < K){
node.right = null;
}
return total_value;
}

なぜ今私はそれらを削除することができますか？ 左または右のサブツリーから値が返ってくると、そのサブツリーは「終了」し、処理され、重要なことがあります。それによって、そのサブツリーすべてが追加されます。したがって、このノードのtotal_valueがKより小さい場合は、このノードを意味し、このノードのすべての子（および子の子など）がK未満です。原因subtreeの子が私に値を返すとき、その子はtotal_valueすべてのサブツリーの値を格納します。

Approchはツリーをトラバースしてノードを削除することですボトムアップ方式で。ツリーをトラバースする際に、各パスのルートノードからリーフノードへのノードの合計を再帰的に計算します。訪問先ノードごとに、計算された総和と所定の合計「k」とを比較する。もしsumがkより小さければ、そのノード（葉ノード）を解放（削除）し、その合計を前のノードに返す。

public int removeNodesUtil(Node node, int sum, int k)
{
if (node == null) return sum;

sum =sum + node.data;
if (node.left == null && node.right == null)
{
if (sum < k)
{
node = null;
}
return sum;
}
int leftSum = 0, rightSum = 0, maxSum = 0;

if (node.left != null) {
leftSum = removeNodesUtil(node.left, sum, k);
if (leftSum < k) {
node.left = null;
}
}

if (node.right != null) {
rightSum = removeNodesUtil(node.right, sum, k);
if (rightSum < k) {
node.right = null;
}
}
maxSum = Math.max(leftSum, rightSum);
if (maxSum < k) {
node = null;
}
return maxSum;
}