Сложность: medium
Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева.
Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
(Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)
Пример:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.
👨💻 Алгоритм:
1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.
2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.
3⃣Существует два подхода для выбора двух наибольших высот:
— Первый способ заключается в хранении высот всех дочерних узлов в массиве, последующей сортировке массива и выборе двух наибольших элементов.
— Второй способ использует две переменные, которые отслеживают текущие два наибольших значения. Во время итерации по всем высотам эти переменные обновляются соответствующим образом.
😎 Решение:
class Solution:
def __init__(self):
self.diameter = 0
def height(self, node):
if not node.children:
return 0
maxHeight1, maxHeight2 = 0, 0
for child in node.children:
parentHeight = self.height(child) + 1
if parentHeight > maxHeight1:
maxHeight2 = maxHeight1
maxHeight1 = parentHeight
elif parentHeight > maxHeight2:
maxHeight2 = parentHeight
distance = maxHeight1 + maxHeight2
self.diameter = max(self.diameter, distance)
return maxHeight1
def diameter(self, root):
self.diameter = 0
self.height(root)
return self.diameter
Ставь 👍 и забирай 📚 Базу знаний