c++ - 将值从叶传播到根

Question

我已经解决了很多与树有关的问题，但是，我仍然对树的一个特定方面(一般递归)没有信心:

How do you propagate values from the leaf to the root?

例如，假设我们有一棵二叉树，其中我们必须找到具有最小总和的根到叶的路径。对于 TreeMap 像 here ，总和将为 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?
}

我知道最后一个 return currVal 是不正确的 - 但我应该返回什么？从技术上讲，我只想在到达叶节点时返回 minVal 的值(在中间节点时不返回任何值)。那么，如何将 minVal 从叶节点传播到最顶层的 root 节点？

P.S.:我正在准备面试，这对我来说是一个很大的痛点，因为我几乎每次都卡在这一点上。我将不胜感激任何帮助。谢谢。

编辑:对于这个特别的，我以某种方式 wrote a solution使用引用传递。

Answer 1

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

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

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

编辑:解释

我将使用 tree你在你的问题中提供了一个例子。我们将从在根 (0) 处进入树开始。它会给currVal加0，不会输入第一个if，然后输入for。一旦它在那里，该函数将从第一个 child 再次调用。

在第一个节点 (5)，它会添加那个值，检查它是否结束，然后转到下一个节点 (4)，再次添加，currVal 现在是 9。然后，因为 (4) 没有 children ，它将返回 min(currVal, minVal)。此时minVal为INT_MAX，所以返回9。

一旦这个值被返回，我们回到调用它的函数，它在节点(5)，恰好在我们调用(4)的时候，我们将(通过我的修改)比较哪个值它返回了 minVal。

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

在这一点上，重要的是要注意当前的 minVal 仍然是 INT_MAX，因为它不是一个引用，这是传递给函数的值。因此，我们现在将其设置为 9。

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

从那里，我相信你可以猜到会发生什么，我们进入节点 (3)，它分支到 (2)->(1)->(1) 和 (0)->(10)，返回 7 和 13分别到 for 循环，节点 (6) 最终也会将 7 返回到 (0) 的 for 循环。

最后，(0) 将首先将 INT_MAX 与 9 进行比较，然后与 7 进行比较，最后再次与 7 进行比较，将 7 返回给 getCheapestCost。

简而言之:

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

一旦进入父节点，您需要检查哪些子节点提供了最小 minVal，方法是将其与您之前的 minVal(来自其他子节点、分支或 INT_MAX)进行比较.检查完所有子节点后，minValue 返回给下一个父节点，下一个父节点与它的子节点进行比较，直到到达根节点。