Для каждого узла в сбалансированном двоичном дереве максимальная разница высот левого дочернего поддерева и правого дочернего поддерева не превышает 1.
Высота бинарного дерева - это расстояние от корневого узла до дочернего узла, который находится дальше всего от корня.
Ниже приведен пример:
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4
Высота бинарного дерева: 4
Ниже приведены двоичные деревья и отчет о том, сбалансированы они или нет:
Дерево выше не сбалансировано .
Вышеуказанное дерево сбалансировано .
Напишите самую короткую возможную программу, которая принимает в качестве входных данных корень двоичного дерева и возвращает ложное значение, если дерево не сбалансировано, и истинное значение, если дерево сбалансировано.
вход
Корень бинарного дерева. Это может быть в форме ссылки на корневой объект или даже списка, который является допустимым представлением двоичного дерева.
Выход
Возвращает истинное значение: если дерево сбалансировано
Возвращает значение Falsey: если дерево не сбалансировано.
Определение двоичного дерева
Дерево - это объект, который содержит значение и два других дерева или указатели на них.
Структура бинарного дерева выглядит примерно так:
typedef struct T
{
struct T *l;
struct T *r;
int v;
}T;
Если для представления двоичного дерева используется представление списка, оно может выглядеть примерно так:
[root_value, left_node, right_node]
4
, сбалансировано ли оставшееся дерево?Ответы:
Желе , 11 байт
Попробуйте онлайн!
Пустое дерево представлено как
[]
.источник
Пролог (SWI) , 49 байт
Попробуйте онлайн!
Представляет деревья как
Value/Left_Child/Right_Child
, причем атомом является пустое деревоe
. Определяет+/2
, что выводит через успех или неудачу, с несвязанной переменной (или переменной, уже равной высоте дерева) слева и деревом справа - если аргумент высоты недопустим, добавьте 9 байтов для определения-T:-_+T.
.источник
_/
может быть взято за -2 байта.)Wolfram Language (Mathematica) , 50 байтов
Используйте
Null
для нуля,value[left, right]
для узлов. Например, следующее дерево записывается как2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]]
.Попробуйте онлайн!
источник
Python 3.8 (предварительная версия) ,
133125 байтПопробуйте онлайн!
Принимает дерево в формате «список»: узел
[value, left, right]
сleft
иright
узлами является узлами.Вызвать функцию
h
.Возвращает
0
илиFalse
для несбалансированного дерева. Возвращает1
илиTrue
для сбалансированного дерева.Ungolfed:
-10: обратная логика, от которой нужно избавиться
not
сЕсли разрешено принимать аргументы в середине вызова, это можно сократить до (115 байт)
с
_
тем, чтобы быть деревом, чтобы проверить.источник
JavaScript (Node.js) , 49 байт
Попробуйте онлайн!
-9 байтов Арно.
JavaScript, 58 байт
Попробуйте онлайн!
Используйте
[]
для нуля и[left, right, value]
для узлов.источник
JavaScript, 162 байта
Попробуйте онлайн!
Формат ввода - это объект
объяснение
Выполняя поиск в ширину, найдите глубину первого узла, в котором отсутствует одна или несколько ветвей.
Продолжая поиск в ширину, верните ноль, если какой-либо элемент на два глубже, чем глубина пропущенных ветвей первого узла.
Если такой узел не найден, вернуть 1
источник
4
.Юлия, 56 байт
Со следующей структурой, представляющей двоичное дерево:
c
это кортеж, представляющий левый и правый узлы и пустой кортеж()
используется, чтобы сигнализировать об отсутствии узла.Значение Falsey -
NaN
любое целое число является правдивым.источник
≢
, согласно встроенному счетчику байтов TIO . В любом случае, добро пожаловать в CG & CC!Котлин , 67 байт
где
Попробуйте онлайн!
источник
C 117 байт
Структура реализации выглядит следующим образом:
Попробуйте это на JDoodle
источник
<2
вместо этого вы можете выполнить последнюю проверкуPython 2 ,
999694 байтаПопробуйте онлайн!
3 байта от Джо Кинга .
Принимает ввод как: пустой узел есть
[]
, а другие узлы есть[<value>, <leftNode>, <rightNode>]
. Выходы0/1
для False / True.источник