Решение проблем Neetcode 150 (Сегодняшняя проблема: диаметр двоичного дерева)

Учитывая root бинарного дерева, вернуть длину диаметра дерева.

Диаметр бинарного дерева – это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через root.

Длина пути между двумя узлами представлена ​​количеством ребер между ними.

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Чтобы найти диаметр бинарного дерева, вы можете использовать рекурсивный подход. Вот пример реализации на Kotlin:

fun diameterOfBinaryTree(root: TreeNode?): Int {
    var maxDiameter = 0
    fun dfs(node: TreeNode?): Int {
        if (node == null) return 0
        val left = dfs(node.left)
        val right = dfs(node.right)
        maxDiameter = maxOf(maxDiameter, left + right)
        return maxOf(left, right) + 1
    }
    dfs(root)
    return maxDiameter
}

Функция принимает на вход корневой узел бинарного дерева и возвращает диаметр дерева. Функция использует вспомогательную функцию dfs(node: TreeNode?), которая вызывается рекурсивно на каждом узле дерева. Эта функция возвращает высоту поддерева с корнем в данном узле. Во время обхода функция отслеживает максимальный диаметр, наблюдаемый до сих пор, и обновляет его всякий раз, когда обнаруживается новый диаметр.

Обратите внимание, что это решение имеет временную сложность O(n), поскольку оно посещает все узлы дерева один раз.

Вы также можете решить эту проблему с временной сложностью O(n) и пространственной сложностью O(n) с помощью динамического программирования.

Стоит отметить, что существуют и другие способы нахождения диаметра бинарного дерева, такие как использование обхода по уровням или модифицированного обхода в прямом порядке. Реализация, которую вы выберете, будет зависеть от конкретных требований вашей проблемы и компромиссов, на которые вы готовы пойти с точки зрения сложности времени и пространства.

Проверьте мой репозиторий GitHub для более решенных проблем: -

Удачного кодирования :)