将值从叶传播到根

Question

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

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

例如，假设我们有一棵二叉树，其中我们必须找到具有最小总和的根到叶的路径。对于树形图像 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 不正确 - 但我应该 return 做什么？从技术上讲，当我到达叶节点时，我只想 return minVal 的值（当我在中间节点时没有值）。那么，如何将 minVal 从叶节点传播到最顶层的 root 节点？

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

编辑：对于这个特定的，我不知何故 wrote a solution 使用了引用传递。

Answer 1

在您的 for 中保存所有 children 和 return minVal 而不是 currVal 的 minVal。

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

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

编辑：解释

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

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

一旦这个值被returned，我们回到调用它的函数，它在节点（5），恰好在我们调用（4）的时候，我们将（经过我的修改）比较它 returned 与 minVal 的任何值。

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

此时，请务必注意当前的 minVal 仍为 INT_MAX，因为它不是引用，而是传递给函数的值。因此，我们现在将其设置为 9。

如果 (5) 有其他 children，我们现在将输入 dfs 的新实例，一旦我们得到结果，将该值与9，但因为我们不这样做，所以我们结束 for 循环和 return minVal，回到根节点（0 ).

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

最后，(0) 会先比较 INT_MAX 和 9，然后比较 7，最后再比较 7，returning 7 to getCheapestCost.

简而言之：

你的代码会一直进入dfs直到它找到一个没有children的节点，一旦发生这种情况，它将return minVal 它从该节点获得，return 到调用它的函数，即 parent 节点。

进入 parent 节点后，您需要检查哪个 children 提供了最小值 minVal，方法是将其与之前的 minVal（来自其他children、分支或INT_MAX）。检查所有 children 后，minValue 被 returned 到下一个 parent，与它的 children 比较，直到达到根节点。

将值从叶传播到根

Propagating values from the leaf to the root

c++

tree

tree-traversal