110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

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

Задано бинарное дерево. Определите, является ли оно сбалансированным по высоте.

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

class Solution {

public:

bool isBalanced(TreeNode* root) {

}

};

РЕШЕНИЕ

структуры данных - деревья

Анализ алгоритма

Напишем функцию высоты бинарного дерева. Для каждой вершины вычисляем высоту его левого и правого сына. Для выполнения условия сбалансированности эти высоты должны отличаться не более чем на 1. Если это условие для какой-то вершины нарушится, функция Height вернет -1.

Реализация алгоритма

class Solution

{

public:

bool isBalanced(TreeNode* root)

{

return (Height(root) != -1);

}

int Height(TreeNode* root)

{

if(root == NULL)

return 0;

int Left = Height(root->left);

int Right = Height(root->right);

if(Left == -1 || Right == -1 || abs(Left - Right) > 1 )

return -1;

return max(Left,Right) + 1;

}

};