Как найти самый длинный путь, соединяющий два листа в двоичном дереве?

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

  • Функция должна быть рекурсивной и возвращать длину самый длинный путь.
  • Мне нужен только псевдокод

Как найти самый длинный путь, соединяющий два листа в двоичном дереве?

Я только что прочитал, что то, что я ищу, называется Диаметр дерева

Вы имеете в виду «единственный путь», поскольку это дерево? Или, если вы хотите пройти через корень, может ли ваш «путь» вернуться к самому себе?

pkpnd 17.06.2018 18:47

он хочет найти два самых далеких листа.

Marek R 17.06.2018 18:53

@MarekR хорошо понял. Это просто сумма высоты левой части дерева + высота правой части дерева, но я не знаю, как это записать рекурсивно.

RUsl 17.06.2018 18:54
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
3
3
447
1

Ответы 1

Отметим, что диаметр двоичного дерева не обязательно равен длине самого длинного пути через корень. Рассмотрим полное двоичное дерево, которое было изменено путем добавления дополнительного узла к корню - тогда лучший путь вообще не проходит через корень.

Если вы должны пройти через корень, то самый длинный путь - это тот, который идет к самым глубоким узлам в левом и правом поддеревьях. Так что подумайте о написании вспомогательной функции, которая находит самый глубокий узел в поддереве, и посмотрите, сможете ли вы использовать это в качестве отправной точки.

Другие вопросы по теме