删除所有不在任何路径上且 sum>= k 的节点

Question

我在这里阅读主题并阅读代码- http://www.geeksforgeeks.org/remove-all-nodes-which-lie-on-a-path-having-sum-less-than-k/

但是我卡在了一个点上。在代码的以下功能中：

struct Node *pruneUtil(struct Node *root, int k, int *sum)
{
    // Base Case
if (root == NULL)  return NULL;

// Initialize left and right sums as sum from root to
// this node (including this node)
int lsum = *sum + (root->data);
int rsum = lsum;

// Recursively prune left and right subtrees
root->left = pruneUtil(root->left, k, &lsum);
root->right = pruneUtil(root->right, k, &rsum);

// Get the maximum of left and right sums
*sum = max(lsum, rsum);

// If maximum is smaller than k, then this node
// must be deleted
if (*sum < k)
{
    free(root);
    root = NULL;
}

return root;
}

// A wrapper over pruneUtil()
struct Node *prune(struct Node *root, int k)
{
    int sum = 0;
return pruneUtil(root, k, &sum);
}

我有以下两个问题：

在函数*prune中，我们调用函数pruneUTIL发送sum的地址然后在函数pruneUTIL中，我们使用*sumeverywhere.Why发送sum地址？使用 address of sum 有什么意义？
我们为什么不发送简单的整数 sum？
为什么要计算 lsum 和 rsum 的最大值？

有人可以解决问题吗？

Answer 1

使用指向 sum 变量的指针的要点是变量 sum 将是可修改的。如果您只发送一笔款项，那么函数 returns 时不会反映价值的变化。例如

    int main()
    {
      int v=1;
      goot(v);
      gootp(&v)l
    }
    void goot(int val)
    {
      val=10;
    }
    void gootp(int * val)
    {
      *val=10;
    }

goot后returnv的值不会是10，会保持为1 但是当调用 gootp 时，该值将被修改为 10.

在这里我们希望每个节点的变化都得到反映，我们希望总和是到达任何叶子所采用的所有路径的最大值+从根到节点的计算值我们可以简单地拥有return编辑了值，但这里我们要删除节点，所以我们需要 return 节点，如果它们为空，那么 left/right 子节点需要修改，因为只有一件事可以是 returned 所以我们使用指向这个变量的指针

所以我们不发送变量 sum，因为当函数 pruneUtil return 用于节点的左右子节点时，为这些子树计算的 sum 值将丢失。这样我们就可以比较路径的总和，因为我们需要在节点下面加上节点的值来计算路径的总和。如果我们只是发送一个变量，它的变化在父函数中是看不到的（因为我们不能 return 值，因为它被用于 return 节点）。
我们计算左和右的最大值，因为对于一个节点，有两条路径通过它的左节点和另一条路径通过它的右子节点指向叶节点（这些路径会进一步分开）所以如果其中任何一个这些路径的总和值 > k 那么我们不需要删除该节点。所以我们为每个节点取左和右的最大值，所以对于每个节点，我们得到从根到叶的路径的最大值。

删除所有不在任何路径上且 sum>= k 的节点

Remove all nodes which don’t lie in any path with sum>= k

algorithm

tree

binary-tree

data-structures