Условие

Дано N-арное дерево, требуется найти его максимальную глубину. Глубина дерева — это максимальное количество узлов от корня до самого дальнего листа.

Примеры

Input: root = [1, null, 3, 2, 4, null, 5, 6] Output: 3

Input: root = [1, null, 2, 3, 4, 5, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] Output: 5

Решение

/**
 * Example:
 * var ti = Node(5)
 * var v = ti.`val`
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var children: List<Node?> = listOf()
 * }
 */
fun maxDepth(root: Node?): Int {
    // Если дерево пустое, то его глубина равна 0
    if (root == null) return 0

    // Изначальная глубина текущего узла
    var maxDepth = 0

    // Рекурсивно вычисляем глубину для каждого дочернего узла
    for (child in root.children) {
        maxDepth = maxOf(maxDepth, maxDepth(child))
    }

    // Глубина текущего узла равна 1 (сам узел) плюс максимальная глубина его дочерних узлов
    return maxDepth + 1
}

Временная сложность

O(n) — Проходим по каждому узлу дерева один раз, где n — количество узлов в дереве.

Пространственная сложность

O(h) — Используется стек рекурсии, где h — высота дерева (в среднем O(log n), в худшем случае O(n)).