Условие

Дано бинарное дерево, требуется найти диаметр дерева. Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами. Длина пути определяется числом ребер на этом пути.

Примеры

Input: root = [1, 2, 3, 4, 5] Output: 3 Explanation: Длина самого длинного пути — это путь [4, 2, 1, 3] или [5, 2, 1, 3], состоящий из 3 ребер.

Input: root = [1, 2] Output: 1

Решение

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
fun diameterOfBinaryTree(root: TreeNode?): Int {
    var diameter = 0

    // Вспомогательная функция для вычисления высоты поддерева и обновления диаметра
    fun height(node: TreeNode?): Int {
        if (node == null) return 0

        // Рекурсивно вычисляем высоту левого и правого поддеревьев
        val leftHeight = height(node.left)
        val rightHeight = height(node.right)

        // Обновляем диаметр, если текущий путь длиннее
        diameter = maxOf(diameter, leftHeight + rightHeight)

        // Возвращаем высоту текущего узла
        return maxOf(leftHeight, rightHeight) + 1
    }

    // Запускаем вычисление высоты дерева
    height(root)

    return diameter
}

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

O(n) — Проходим все узлы дерева один раз.

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

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