Найдите минимальные затраты для посещения всех узлов дерева.

Question

Учитывая корень дерева, в котором у каждого края есть соответствующая стоимость. Найдите минимальную стоимость для посещения каждого узла дерева.

Рекурсивный решение, которое пришло мне в голову:

1. базовый случай, когда узел является листом возврата 0.
2. для каждого ребенка с узла рекурсивно вычислить стоимость.
3. добавьте все эти затраты, а также дважды добавьте стоимость края от узла к ребенку (как нам нужно для возврата).
4. вычитаем стоимость края ребенка, у которого максимальная стоимость. («Жадный» - мы не хотим отступать от ребенка с максимальной стоимостью).

Правильно ли этот подход?

Есть ли лучший способ решить эту проблему?

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- как только мы найдем это, нам нужно будет сделать наш обход таким образом, чтобы этот листовой узел был последним посещенным узлом.