Найти вершины дерева , через которые проходят наибольшее количество путей максимальной длины
Найти вершины дерева , через которые проходят наибольшее количество путей максимальной длины.
Функция этой задачи возвращает поддерево через которое проходят искомые вершины.
Понимаю как найти максимальный путь дерева, думаю , что нужно находить все максимальные деревья у левого и правого поддерева от исходного дерева. Но вот не могу понять как найти пересечения этих максимальных путей. Может изначально неправильно думал ,больше идей нет.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
- Нашли максимальную длину пути
- Обошли все пути максимальной длины, на каждом шаге увеличивая на единицу счетчик в узлах, через которые пробегаем
- Выбрали узлы с максимальным счётчиком