1382. Balance a Binary Search Tree

Задача

Дан корень BST. Верните сбалансированный BST с теми же значениями.

Примеры

Пример 1

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

Пояснение

Это не единственный правильный ответ, [3,1,4,null,2] тоже корректен.

Пример 2

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

Решение

Решение

/**
 * Временная сложность: O(n)
 * 1. treeToArr (Inorder Traversal):
 *    - Мы посещаем каждый узел ровно один раз, выполняя O(1) работы (push)
 *    - Это занимает O(n), где n - количество узлов
 * 
 * 2. arrToTree (Построение сбалансированного дерева):
 *    - Функция вызывается для каждого элемента массива ровно один раз (каждый элемент становится узлом)
 *    - Вычисление mid и создание new TreeNode занимает O(1)
 *    - Итого построение занимает O(n)
 * 
 * Итоговое время: O(n) + O(n) = O(n)
 * 
 * Пространственная сложность: O(n)
 * 1. arr: хранит n значений узлов -> O(n)
 * 2. Стек рекурсии для treeToArr:
 *    - O(h) в худшем случае для исходного дерева (если оно вырождено в список, то O(n))
 * 3. Стек рекурсии для arrToTree:
 *    - Мы строим сбалансированное дерево, поэтому высота будет log(n) -> O(log n)
 * 
 * Итоговая память: O(n) (доминирует массив arr)
 */
var balanceBST = function(root) {
    const arr = [];
 
    function treeToArr(node) {
        if (!node) return;
 
        treeToArr(node.left);
        arr.push(node.val);
        treeToArr(node.right);
    }
 
    function arrToTree(left, right) {
        if (left > right) return null;
 
        // (left + right) / 2 тоже работает, но этот вариант защищает от переполнения
        // (хотя в JS числа 64-бит float, переполнение маловероятно для arr.length)
        const mid = left + Math.floor((right - left) / 2);
        const node = new TreeNode(arr[mid]);
 
        node.left = arrToTree(left, mid - 1);
        node.right = arrToTree(mid + 1, right);
 
        return node;
    }
 
    treeToArr(root);
    // console.log(arr); // Для отладки
    return arrToTree(0, arr.length - 1);
};