Задача: 1382. Balance a Binary Search Tree
Сложность: medium

Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них.

Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

👨‍💻 Алгоритм:

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    function balanceBST($root) {
        if (!$root) return null;

        $vineHead = new TreeNode(0);
        $vineHead->right = $root;
        $current = $vineHead;

        while ($current->right) {
            if ($current->right->left) {
                $this->rightRotate($current, $current->right);
            } else {
                $current = $current->right;
            }
        }

        $nodeCount = 0;
        $current = $vineHead->right;
        while ($current) {
            $nodeCount++;
            $current = $current->right;
        }

        $m = pow(2, floor(log($nodeCount + 1, 2))) - 1;
        $this->makeRotations($vineHead, $nodeCount - $m);
        while ($m > 1) {
            $m /= 2;
            $this->makeRotations($vineHead, $m);
        }

        return $vineHead->right;
    }

    private function rightRotate($parent, $node) {
        $tmp = $node->left;
        $node->left = $tmp->right;
        $tmp->right = $node;
        $parent->right = $tmp;
    }

    private function leftRotate($parent, $node) {
        $tmp = $node->right;
        $node->right = $tmp->left;
        $tmp->left = $node;
        $parent->right = $tmp;
    }

    private function makeRotations($vineHead, $count) {
        $current = $vineHead;
        for ($i = 0; $i < $count; $i++) {
            $tmp = $current->right;
            $this->leftRotate($current, $tmp);
            $current = $current->right;
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний