Сложность: 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 {
protected int diameter = 0;
protected int height(Node node) {
if (node.children.size() == 0)
return 0;
int maxHeight1 = 0, maxHeight2 = 0;
for (Node child : node.children) {
int parentHeight = height(child) + 1;
if (parentHeight > maxHeight1) {
maxHeight2 = maxHeight1;
maxHeight1 = parentHeight;
} else if (parentHeight > maxHeight2) {
maxHeight2 = parentHeight;
}
int distance = maxHeight1 + maxHeight2;
this.diameter = Math.max(this.diameter, distance);
}
return maxHeight1;
}
public int diameter(Node root) {
this.diameter = 0;
height(root);
return diameter;
}
}Ставь 👍 и забирай 📚 Базу знаний