查找访问树的所有节点的最小开销

Question

给定每个边都有相关成本的树的根。查找访问树的每个节点的最低成本。

是来到我的脑海递归的解决方案是：当节点是节点递归地计算成本的每一个孩子℃的叶返回0

1. 基本情况。
2. 合计所有这些成本，并且还将两次从节点到小孩的边缘成本加起来（因为我们需要回溯）。
3. 减去成本最高的孩子的边缘成本（“贪婪” - 我们不想从成本最高的孩子回溯）。

该方法是否正确？

有没有更好的方法来解决问题？

Answer 1

1. 访问从节点和返回该节点的所有子树，这将花费所有edges * 2属于该子树。
2. 所以我们应该在树中找到路径成本最大的路径。我们只是通过路径，如果我们遇到了一些不在路径中的节点，我们只是访问它并且返回。 所以路径中的边只会访问一次，剩下的边将访问两次。
3. 如何找到成本最高的路径？既然它是一棵树，你可以递归地找到它。

答案应该是：

sum(cost(edge)*2) - sum(edge which in the path) 

---

我检查你的解决方案，我认为这是错误的（如果我误解你的解决方案，请留言）：

减（“贪婪” - 我们不希望从儿童回溯，成本最高）。

那孩子会是树，有些边缘必须访问两次。例如：

A 
/\ 
    B C 
/\ 
D E 

您无法访问该子树的所有边一次访问所有节点。

Answer 2

1-除最后一个叶节点外，所有节点路径都将被访问两次。

2-我们将需要找出哪个叶节点具有最高的成本附加访问根节点。

3-一旦我们发现这一点，我们将需要使我们的遍历，使这个叶节点是最后访问的节点。