LeetCode 110- Сбалансированное бинарное дерево

Вопрос:

Учитывая бинарное дерево, определите, сбалансировано ли оно по высоте.

Для этой задачи сбалансированное по высоте бинарное дерево определяется как:

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

Пример 1:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Решение:

В данной задаче мы должны проверить, сбалансировано ли дерево по высоте или нет.

Сбалансированное по высоте дерево — это дерево, в котором разница высоты левого и правого поддеревьев не превышает 1.

Во-первых, мы проверим, является ли корень нулевым. Если да, то мы вернем true.

if(root == NULL)
    return true;

Мы создадим две переменные, leftH и rightH, для хранения высоты левого и правого поддеревьев соответственно. Другая переменная, diff, будет создана для хранения абсолютной разницы между leftH и rightH.

int leftH = height(root -> left);
int rightH = height(root -> right);
int diff = abs(rightH - leftH);

Теперь мы вернем true, если diff меньше или равен 1, а левое и правое поддеревья сбалансированы.

return diff <= 1 && isBalanced(root -> left) && isBalanced(root -> right);

Последний шаг — создать функцию для вычисления высоты дерева.

Здесь мы сначала проверим, является ли корень нулевым. Если да, вернуть 0.

int height(TreeNode* root)
{
    if(root == NULL)
        return 0;

Если корень не равен null, то мы вернем максимум из высоты левого поддерева и правого поддерева. И 1 будет добавлено к максимальному значению.

else
    return 1 + max(height(root -> left), height(root -> right));
}

Ниже приведен полный код для данной проблемы:

Спасибо за прочтение!

S.