Convert Sorted Array to Binary Search Tree

Условие

Дан отсортированный по возрастанию массив уникальных целых чисел. Необходимо написать функцию, которая преобразует этот массив в сбалансированное бинарное дерево поиска. Сбалансированное дерево означает, что глубина двух поддеревьев любого узла отличается не более чем на 1.

Примеры

Input: nums = [-10, -3, 0, 5, 9]

Output: [0, -3, 9, -10, null, 5]

Explanation: [0, -3, 9, -10, null, 5] формирует бинарное дерево поиска:

        0
       / \
     -3   9
     /   /
   -10  5

Input: nums = [1, 3]

Output: [3, 1]

Explanation: [3, 1] формирует следующее бинарное дерево поиска

      3
     /
    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 sortedArrayToBST(nums: IntArray): TreeNode? {
    // Вспомогательная рекурсивная функция для создания дерева
    fun helper(left: Int, right: Int): TreeNode? {
        // Базовый случай: если левая граница больше правой, вернуть null
        if (left > right) return null

        // Выбор среднего элемента массива для корневого узла
        val mid = (left + right) / 2
        val node = TreeNode(nums[mid])

        // Рекурсивное создание левого поддерева из левой половины массива
        node.left = helper(left, mid - 1)

        // Рекурсивное создание правого поддерева из правой половины массива
        node.right = helper(mid + 1, right)

        // Возврат созданного узла
        return node
    }

    // Запуск рекурсивного процесса от всего диапазона массива
    return helper(0, nums.size - 1)
}

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

Построение дерева требует обхода всех элементов массива, а рекурсивное деление массива занимает O(log n) на каждом уровне, где n — длина массива. Таким образом, временная сложность — O(n).

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

Пространственная сложность O(log n), так как глубина рекурсивного стека ограничена глубиной дерева, которая составляет log n для сбалансированного дерева.