Balanced Binary Tree

+10

Массив root содержит двоичное дерево. Корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце могут следовать дополнительные элементы -1.

Верните true, если дерево сбалансировано по высоте, то есть высоты левого и правого поддеревьев отличаются не более чем на 1 в каждом узле, и false в противном случае. Высота поддерева — это количество узлов на его самом длинном нисходящем пути; высота пустого поддерева равна 0.

Функция

isBalanced(root: integer-array) → boolean

rootinteger-array: двоичное дерево в порядке уровней, где -1 обозначает пустое место
Возвращаетboolean: true, если высоты двух поддеревьев каждого узла отличаются не более чем на 1, иначе false

Ограничения

1 ≤ root.length ≤ 32767
Каждый root[i] равен -1 или значению, для которого 0 ≤ root[i] ≤ 10⁵.
root[0] никогда не равно -1, поэтому у дерева есть как минимум один узел.
После последнего узла в массиве могут быть лишние элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
Значения узлов различны.

Примеры

Ввод: root = [5, 2, 9, -1, -1, 7, 11]
Вывод: true
Пояснение: Левое поддерево корня — это единственный узел 2, его высота — 1. Его правое поддерево 9, 7, 11 имеет высоту 2. Их высоты различаются на 1, а у всех остальных узлов высоты двух поддеревьев равны.

Ввод: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Вывод: false
Пояснение: Обе стороны корня имеют высоту 3, но узел 3 не проходит проверку: его левое поддерево 1, 0 имеет высоту 2, а правое пусто.

Ввод: root = [4, 2, -1, 1]
Вывод: false
Пояснение: У корня слева находится цепочка 2, 1 высотой 2, а справа ничего нет — высота 0. Разница 2 слишком велика.

Дополнительный вопрос

Можешь проверить дерево без рекурсии, используя явный стек?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Правило применяется к каждому узлу, поэтому дерево, корень которого выглядит чётным, всё равно может не пройти проверку ниже, как это происходит во втором примере на узле 3. Обход в обратном порядке вычисляет высоту каждого поддерева один раз и передаёт информацию о нарушении вверх, как только оно обнаруживается, за O(n).

Пересчитайте высоты в каждом узле

Идея

Преврати определение в код. height(i) равно 0 в пустой позиции, а в остальных случаях на 1 больше высоты более высокого дочернего узла. Сравнивай высоты двух дочерних узлов в каждом существующем узле; первый узел, в котором они различаются более чем на 1, даёт ответ false.

Каждая проверка обходит всё поддерево под своим узлом, поэтому каждый узел обходится один раз для каждого узла над ним: O(n·h). При высоте не более 14 уровней полный список из 16,383 узлов требует около 2 × 10^5 шагов. Цепочка из n узлов потребует O(n²).

Алгоритм

Определите height(i) как 0 для индекса за пределами конца или -1, а для реального узла — как 1 + max(height(2*i+1), height(2*i+2)).
Посетите каждый индекс i, содержащий реальный узел.
Если height(2*i+1) и height(2*i+2) различаются более чем на 1, верните false.
Если цикл завершился без ошибки, верните true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Один обход в обратном порядке, который сообщает высоту или неудачу

Идея

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

Ошибка в нижней части дерева тоже должна передаваться вверх. Реальная высота никогда не бывает отрицательной, поэтому будем использовать -1 для обозначения ошибки: вызов возвращает -1, если дочерний узел вернул -1 или высоты дочерних поддеревьев различаются более чем на 1. Во втором примере узел 3 видит высоты 2 и 0 и возвращает -1, а корень передаёт это значение дальше, не обходя правую сторону.

Ни один узел не посещается дважды, поэтому временная сложность составляет O(n), а в стеке находится O(h) вызовов.

Алгоритм

Напишите check(i). Для индекса за пределами конца или значения -1 верните 0.
Вычислите left = check(2*i+1). Если это -1, верните -1.
Вычислите right = check(2*i+2). Если это -1 или left и right отличаются более чем на 1, верните -1.
В противном случае верните 1 + max(left, right).
Верните, является ли check(0) значением, отличным от -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Ловушки и крайние случаи

Проверять только корень. Во втором примере высота обеих сторон корня равна 3, однако узел 3 отклоняется на 2.
Сравнивать самую мелкую и самую глубокую листовую вершину. В самом маленьком сбалансированном дереве высоты 6 листья находятся на глубине 4 и 6, и проверку проходит каждый узел.
Терять информацию об ошибке при подъёме вверх. Если дочерний узел возвращает -1, а родитель вычисляет 1 + max(-1, 2), признак ошибки снова превращается в высоту.
Использовать длину массива в качестве высоты. Хвостовые элементы -1 делают массив длиннее, чем глубина дерева.
В Lua и R массивы начинаются с 1. Сохраняйте индексы узлов начинающимися с 0 для 2*i+1 и считывайте root[i + 1].

Частые вопросы3

Какова временная сложность сбалансированного бинарного дерева?

Один обход в постфиксном порядке посещает каждый узел один раз: время O(n) и место в стеке O(h) для дерева высотой h. Повторный расчёт высоты в каждом узле требует O(n·h), что для цепочки превращается в O(n²).

Что означает сбалансированность по высоте для бинарного дерева?

В каждом узле высоты левого и правого поддеревьев отличаются не более чем на 1. AVL-деревья восстанавливают это свойство после каждой вставки и удаления, благодаря чему их высота остаётся равной O(log n).

Всегда ли полное бинарное дерево сбалансировано?

Да. Каждый уровень полного дерева заполнен, за исключением, возможно, последнего, который заполняется слева направо, поэтому в любом узле высоты двух поддеревьев различаются не более чем на 1. Обратное неверно: у сбалансированного дерева на последнем уровне могут быть пропуски слева.

def isBalanced(root):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

root = [5, 2, 9, -1, -1, 7, 11]

Ожидаемый вывод

true