我已经解决了很多与树木有关的问题，但是，我仍然对树木的某个方面（通常是递归）没有信心：
您如何将值从叶传播到根？
例如，假设我们有一棵二叉树，我们必须以最小的总和找到根到叶的路径。对于树图像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节点？附注：我正在准备面试，这对我来说是一个很大的痛苦领域，因为我几乎每次都被困在这一点上。我将不胜感激。谢谢。
编辑：对于这个特定的对象，我以某种方式通过引用传递wrote a solution。
最佳答案
在您的内部，保存所有子项的minVal并返回minVal而不是currVal。
for(auto& neighbor: rootNode->children) {
minVal = min(minVal, dfs(neighbor, minVal, currVal));
}
return minVal;
这样一来，您始终通过递归一直返回minVal，直到第一次调用。
编辑：解释
我将以您在问题中提供的tree为例。我们将从在根（0）处输入树开始。它将为currVal加0，如果不输入第一个，则输入for。到达该位置后，将从第一个孩子那里再次调用该函数。
在第一个节点（5）上，将添加该值，检查是否为结尾，然后转到下一个节点（4），再次添加，currVal现在为9。然后，由于（4）没有子代，因此它将返回min（currVal，minVal）。此时，minVal为INT_MAX，因此它返回9。
返回此值后，我们将返回到调用它的函数，该函数位于node（5）处，恰好是在调用（4）时的那一点，然后（通过我的修改）我们将比较返回的那个值minVal。
min(minVal, dfs(neighbor, minVal, currVal))
在这一点上，重要的是要注意当前的minVal仍然是INT_MAX，因为它不是引用，而这是传递给函数的值。结果，我们现在将其设置为9。
如果（5）还有其他孩子，我们现在将输入新的dfs实例，并在得到结果后立即将该值与9进行比较，但由于没有，我们结束了for循环并返回minVal，然后返回到根节点（0）。
从那里，我相信您可以猜测会发生什么，我们进入节点（3），该节点分支到（2）->（1）->（1）和（0）->（10），将7和13返回到for最后，节点（6）最终还将返回（0）的for循环的7。
最后，（0）首先将INT_MAX与9比较，然后与7比较，最后再与7比较，将7返回到getCheapestCost。
简而言之：
您的代码将一直输入dfs，直到找到没有子节点的节点为止，一旦发生，它将返回从该节点获得的minVal，并返回到调用它的函数，即父节点。
到达父节点后，您需要通过将最小minVal与以前的minVal（来自其他子节点，分支或INT_MAX）进行比较，来检查哪些子节点提供了最小minVal。在检查完所有子代之后，minValue返回到下一个父代，该父代与其下一个父代进行比较，直到到达根节点为止。
关于c++ - 将值从叶传播到根，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49246363/