как я могу найти длину самого длинного пути, соединяющего два листа через корень в двоичном дереве?
Я только что прочитал, что то, что я ищу, называется Диаметр дерева
он хочет найти два самых далеких листа.
@MarekR хорошо понял. Это просто сумма высоты левой части дерева + высота правой части дерева, но я не знаю, как это записать рекурсивно.
Отметим, что диаметр двоичного дерева не обязательно равен длине самого длинного пути через корень. Рассмотрим полное двоичное дерево, которое было изменено путем добавления дополнительного узла к корню - тогда лучший путь вообще не проходит через корень.
Если вы должны пройти через корень, то самый длинный путь - это тот, который идет к самым глубоким узлам в левом и правом поддеревьях. Так что подумайте о написании вспомогательной функции, которая находит самый глубокий узел в поддереве, и посмотрите, сможете ли вы использовать это в качестве отправной точки.
Вы имеете в виду «единственный путь», поскольку это дерево? Или, если вы хотите пройти через корень, может ли ваш «путь» вернуться к самому себе?