gpt4 book ai didi

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

转载 作者:太空狗 更新时间:2023-10-29 20:45:06 27 4
gpt4 key购买 nike

这是我研究代码中的一个问题,我想知道解决这个问题的有效方法是什么。我将省略不必要的细节,并以一种可以理解问题症结的方式呈现它。

假设我有一个二叉树,每个节点上都有数字。我想找到树中从根到叶的所有分支的最小总和。下面是一个非常粗略的伪代码。

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;
   }
}

关于c++ - 寻找树中最小值的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11553452/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com