Сложность: easy
Дано n-арное дерево, найдите его максимальную глубину.
Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.
Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).
Пример:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3
👨💻 Алгоритм:
1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии.
2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).
3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.
😎 Решение:
class Solution {
maxDepth(root) {
if (root === null) {
return 0;
} else if (root.children.length === 0) {
return 1;
} else {
let heights = root.children.map(child => this.maxDepth(child));
return Math.max(...heights) + 1;
}
}
}Ставь 👍 и забирай 📚 Базу знаний