← К задачам Режим собеседования 20:00
Обычный режим К собеседованию ← Предыдущая Следующая →

5818. Сбалансировано ли дерево

Easy 0 решили
Двоичное дерево задано списком в порядке уровней: у узла с индексом i левый ребёнок — 2·i+1, правый — 2·i+2. Значение -1 означает, что узла нет. Корень — индекс 0. Если в слоте -1, его потомки в дерево не входят.

Дерево сбалансировано, если у каждого узла высота левого и правого поддеревьев отличается не больше чем на 1. Высота пустого места равна 0, лист имеет высоту 1. Несбалансированный узел в любом месте портит всё дерево.

Пустое дерево сбалансировано. Верните true или false.

Примеры:

Вход: tree = [1, 2, 3]
Выход: true
Объяснение: У корня оба ребёнка — листья, высоты 1 и 1.
Вход: tree = [1, 2, -1, 3]
Выход: false
Объяснение: Слева цепочка из двух узлов, справа пусто. Разница высот у корня равна 2.
Вход: tree = []
Выход: true
Объяснение: Пустое дерево считается сбалансированным.

Ограничения:

0 <= tree.length <= 10^4 значение узла от -10^9 до 10^9 и не равно -1 -1 означает отсутствие узла

Теги:

Часто на собесе Деревья

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!