108. Convert Sorted Array to Binary Search Tree

Задача

Дан отсортированный массив nums. Постройте из него сбалансированное по высоте дерево поиска (BST).

Примеры

Пример 1

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

Пояснение

Вариант [0,-10,5,null,-3,null,9] также допустим.

Пример 2

Input: nums = [1,3]
Output: [3,1]

Пояснение

И [1,null,3], и [3,1] — сбалансированные по высоте BST.

Решение

Решение

/**
 * Time Complexity: O(n)
 *   - Посещаем каждый элемент массива ровно один раз для создания узла
 *   - n элементов → n операций создания TreeNode
 * 
 * Space Complexity: O(log n)
 *   - Глубина рекурсии = высота сбалансированного дерева = log₂(n)
 *   - Каждый рекурсивный вызов добавляет фрейм в стек
 *   - Если считать само дерево: O(n) для хранения n узлов
 *   - Auxiliary space (доп. память без учёта выходных данных): O(log n)
 * 
 * @param {number[]} nums - отсортированный массив
 * @return {TreeNode} - корень сбалансированного BST
 */
var sortedArrayToBST = function(nums) {
    function build(left, right) {
        if (left > right) return null;
 
        const mid = Math.floor((left + right) / 2);
        const node = new TreeNode(nums[mid]);
 
        node.left = build(left, mid - 1); // рекурсия для левой половины
        node.right = build(mid + 1, right); // рекурсия для правой половины
 
        return node;
    }
 
    return build(0, nums.length - 1);
};