将值从叶传播到根

Question

我已经解决了很多与树相关的问题，但是，我仍然对树的一个特定方面（通常是递归）没有信心：

如何将值从叶传播到根？

例如，假设我们有一个二叉树，其中我们必须找到具有最小和的根到叶路径。对于此处的树图像，总和将为7（对应于两条路径0-3-2-1-1或0-6-1）。

我编写了以下代码：

struct Node
{
  int cost;
  vector<Node *> children;
  Node *parent;
};

int getCheapestCost( Node *rootNode )
{
  if(!rootNode) return 0;

  return dfs(rootNode, INT_MAX, 0);
}

int dfs(Node* rootNode, int minVal, int currVal) {
  if(!rootNode) return;

  currVal+=rootNode->cost;
  if(rootNode->children.empty()) {
    minVal = min(minVal, currVal);
    return minVal;
  }

  for(auto& neighbor: rootNode->children) {
    dfs(neighbor, minVal, currVal);
  }

  return currVal;    //this is incorrect, but what should I return?
}

我知道最后一次返回的货币不正确，但是我应该返回什么？从技术上讲，我只想在到达叶节点时返回minVal的值（在中间节点时没有值）。那么，如何将minVal从叶节点传播到最顶部的根节点呢？

P、 美国：我正在准备面试，这对我来说是一个很大的痛苦领域，因为我几乎每次都被困在这一点上。如果有任何帮助，我将不胜感激。谢谢

编辑：对于这一个，我不知何故编写了一个使用引用传递的解决方案。

Answer 1

在您的for中保存所有子级的minVal并返回minVal而不是currVal。

for(auto& neighbor: rootNode->children) {
  minVal = min(minVal, dfs(neighbor, minVal, currVal));
}
return minVal;

这样，您总是通过递归返回minVal，一直到第一次调用。

编辑：解释

我将使用您在问题中提供的树作为示例。我们将从在根（0）处输入树开始。它会将0添加到currVal，不会输入第一个if，然后输入for。一旦它出现，该函数将从第一个子级再次调用。

在第一个节点（5），它将添加该值，检查它是否是结束，然后转到下一个节点（4），再次添加，currVal现在是9。然后，由于（4）没有子项，它将返回min（currVal，minVal）。此时，minVal是INT\u MAX，因此它返回9。

一旦返回这个值，我们就返回到调用它的函数，它位于节点（5），正好在我们调用（4）的时候，我们将（经过修改）将它返回的值与minVal进行比较。

min(minVal, dfs(neighbor, minVal, currVal))

此时，需要注意的是，当前minVal仍然是INT\u MAX，因为它不是引用，而这是传递给函数的值。因此，我们现在将其设置为9。

如果（5）有其他子节点，我们现在将输入一个新的dfs实例，一旦我们有了结果，将该值与9进行比较，但由于我们没有，我们结束for循环并返回minVal，返回根节点（0）。

从那里，我相信你可以猜到会发生什么，我们输入节点（3），它分支到（2）-

最后，（0）将首先将INT_MAX与9进行比较，然后与7进行比较，最后再次与7进行比较，返回7以获得最便宜的成本。

简而言之：

您的代码将继续输入dfs，直到找到一个没有子节点的节点，一旦发生这种情况，它将返回从该节点获得的minVal，并返回调用它的函数，即父节点。

进入父节点后，需要通过将最小值与之前的最小值（来自其他子节点、分支或INT_MAX）进行比较来检查哪些子节点提供了最小最小值。检查完所有子节点后，minValue返回给下一个父节点，该父节点与其子节点进行比较，直到到达根节点。