Сложность: 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:
def balanceBST(self, root: TreeNode) -> TreeNode:
if not root:
return None
vineHead = TreeNode(0)
vineHead.right = root
current = vineHead
while current.right:
if current.right.left:
self.rightRotate(current, current.right)
else:
current = current.right
nodeCount = 0
current = vineHead.right
while current:
nodeCount += 1
current = current.right
m = 2 ** (nodeCount + 1).bit_length() - 1
self.makeRotations(vineHead, nodeCount - m)
while m > 1:
m //= 2
self.makeRotations(vineHead, m)
return vineHead.right
def rightRotate(self, parent, node):
tmp = node.left
node.left = tmp.right
tmp.right = node
parent.right = tmp
def leftRotate(self, parent, node):
tmp = node.right
node.right = tmp.left
tmp.left = node
parent.right = tmp
def makeRotations(self, vineHead, count):
current = vineHead
for _ in range(count):
tmp = current.right
self.leftRotate(current, tmp)
current = current.right
Ставь 👍 и забирай 📚 Базу знаний