Где применяется
1. Задача
Возьми два узла дерева, которые дальше всего друг от друга. Сколько шагов между ними? В оргструктуре это два сотрудника, путь между которыми проходит через больше всего уровней начальников. В сети, устроенной как дерево, это наибольшее число переходов между двумя компьютерами. Это наибольшее расстояние называется диаметром.
Сложность в том, что самый длинный путь часто не проходит через корень. Он может подняться по одной ветке до узла где-то в середине дерева, повернуть там и спуститься по другой ветке.
Сначала простая разминка на том же дереве: сколько в нём листьев, то есть узлов без детей? В дереве папок листья это файлы, в оргструктуре это сотрудники, у которых нет подчинённых.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на дерево, где лучший путь может изгибаться в любом узле, а не только в корне. Вспомогательная функция возвращает родителю одно значение, например высоту, и попутно обновляет лучший ответ для всего дерева.
diameter из урока под тем же именем, считается в рёбрах.
countLeaves, который ещё проверяет, висит ли лист слева, и прибавляет его значение.
Помощник из diameter, только высота ребёнка идёт в счёт, лишь когда у него то же значение.
Та же форма, только суммы вместо высот, а отрицательную ветку отбрасываешь через max с 0.