Поисковое дерево

[xolms]

Найти все пути длины h, соединяющие листья дерева (h – высота дерева). Среди корней этих путей выбрать те, которые расположены на максимальной глубине, и удалить (правым удалением) тот из них, который является средним по значению.

Помогите построить алгоритм действия. Вся сложность состоит втом, что путь длины h, а не максимальный или минимальный

[worm2]

Я так понимаю, путь не должен проходить дважды через одно и то же ребро?

Тогда здесь поиск в ширину должен помочь. Учитывая, что в дереве путь от любой вершины до любой другой единственен, достаточно найти множество листов, доступных за h шагов.
Перед каждым шагом у нас есть множество текущих вершин, множество посещённых вершин и (оставшиеся) множество непосещённых вершин.
На шаге рассматриваем все непосещённые вершины, делаем их текущими, а текущие делаем посещёнными.
На h-м шаге у нас будет множество вершин, доступных за h шагов (=путей длины h). Выбираем из них листы, дальше простой перебор.

[xolms]

Спасибо за ответ, но видимо Вы недопоняли условие. Вообще нужно это сделать за два прохода дерева. Алгоритмы я нашел, но все они порядка

n^2

. Хотел по меньше сложность найти(n-колличество вершин)