c++ - 在树中找到最小值的路径

这是我的研究代码中的一个问题，我想知道执行此操作的有效方法是什么。我遗漏了不必要的细节，并以某种方式进行介绍，以便可以理解问题的症结所在。

可以说我有一棵在每个节点上都有数字的二叉树。我想找到树中从根到叶的所有分支的最小和。下面是一个非常粗糙的伪代码。

int minimum(tree){
   // Some base cases
   left_min = minimum(tree->left);
   right_min= minimum(tree->right);
   if (left_min < right_min){
      return current_value + left_min;
   }
   else{
      return current_value + right_min;
   }
}

由此，我可以计算出最小值。但是，如果我要计算给我最少的节点，我将如何处理？即，如果答案是14，我想找出树中每个级别上的哪些节点加起来得出的总和为14。什么是最有效的方法，而只需对现有功能进行最小的更改？通过最小的更改，我的意思是我可以添加其他变量来跟踪分支，但不能完全重写该函数。

谢谢

最佳答案

您可以使用列表或堆栈或队列来代替 vector :

typedef vector<yourIdType> idvec;

int minimum(tree, idvec &path){
   // Some base cases
   idvec leftPath, rightPath;
   left_min = minimum(tree->left, leftPath);
   right_min= minimum(tree->right, rightPath);
   if (left_min < right_min){
      swap(path, leftPath);
      path.push_back(thisNodeId);
      return current_value + left_min;
   } else {
      swap(path, rightPath);
      path.push_back(thisNodeId);
      return current_value + right_min;
   }
}