Напишите функцию, которая возвращает true, если входное двоичное дерево сбалансировано по высоте, и false, если это не так.
Решение кажется очевидным, мы просто по порядку проходим по дереву ввода и вычисляем левую и правую высоты, мы уже видели, как найти высоты с помощью рекурсии в предыдущем решение здесь,при этом нам просто нужно добавить еще одно условие, чтобы проверить, не нарушает ли какой-либо узел условие высоты.
Условие = (высота левого поддерева — высота правого поддерева) ≤ 1
Мы определим пользовательскую структуру, которая содержит высоту текущего узла.
Наш базовый случай — вернуть структуру с нулевой высотой, так как это был бы конечный узел без дочерних элементов.
Если мы не находимся в листовом узле, то идем налево, как в обходе по порядку, а затем направо.
Чтобы найти текущую высоту, мы береммаксимальную высоту как слева, так и справа идобавляем 1, так как текущий узел на один узел выше, чем его дети.
Код доступен здесь.
Временная сложность равна O(n), где n — количество узлов во входном двоичном дереве.
Сложность пространства равна O(h), где h — самая длинная ветвь во входном двоичном дереве, которая будет помещена в стек вызовов при использовании рекурсии.
