543. Diameter of Binary Tree

Задача

Дан корень бинарного дерева. Верните длину его диаметра (наибольший путь между любыми двумя узлами).

Примеры

Пример 1

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

Пояснение

3 — длина пути [4,2,1,3] или [5,2,1,3].

Пример 2

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

Решение

Решение

/**
 * Time Complexity: O(n)
 * - Посещаем каждую ноду ровно один раз
 * - Для каждой ноды выполняем константное количество операций O(1)
 * - n нод × O(1) работы = O(n) общее время
 * 
 * Space Complexity: O(h), где h — высота дерева
 * - Используется рекурсивный стек вызовов
 * - Максимальная глубина стека = высота дерева
 * - В сбалансированном дереве: O(log n)
 * - В несбалансированном (скewed tree): O(n)
 * - Не используем дополнительные структуры данных (кроме одной переменной maxDiameter)
 */
function diameterOfBinaryTree(root) {
    let maxDiameter = 0;
 
    function calculateHeight(node) {
        if (!node) return 0;
 
        const leftHeight = calculateHeight(node.left);
        const rightHeight = calculateHeight(node.right);
 
        // Обновляем максимальный диаметр
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
 
        // Возвращаем высоту текущего узла
        return 1 + Math.max(leftHeight, rightHeight);
    }
 
    calculateHeight(root);
    return maxDiameter;
}