JuniorКодОчень частоЕщё не отвечали
Проверьте, является ли бинарное дерево сбалансированным
Дан корень бинарного дерева. Верните true, если оно сбалансировано по высоте: в каждом узле высоты левого и правого поддеревьев отличаются не больше чем на 1.
Требования:
- O(n) время — не пересчитывайте высоту поддеревьев в каждом узле (это O(n²)).
- Проверяйте каждый узел, а не только детей корня.
- Пустое дерево считается сбалансированным.
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
bool isBalanced(TreeNode* root) {
// ваш код здесь
}Допишите реализацию.
В каждом узле высоты левого и правого поддеревьев отличаются не больше чем на 1. Оптимальный O(n) DFS возвращает высоту поддерева либо −1 как sentinel для «несбалансировано», совмещая вычисление высоты и проверку баланса в одном проходе.
- ✗Использовать подход O(n²) с отдельной функцией высоты, вызываемой в каждом узле
- ✗Проверять только детей корня, не рекурсивно каждый узел
- ✗Не возвращать sentinel-значение — возврат просто bool теряет информацию о высоте, нужную родителю
- →Что такое AVL-дерево и как оно поддерживает баланс при вставках?
- →В чём разница между деревьями, сбалансированными по высоте и по весу?
Оглавление
Задача
Напишите функцию, которая проверяет, является ли бинарное дерево сбалансированным (разница высот поддеревьев в каждом узле ≤ 1).
Решение
#include <algorithm>
#include <cstdlib>
#include <cassert>
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
explicit TreeNode(int v) : val(v) {}
};
// O(n²) — наивный подход (для иллюстрации)
int height(TreeNode* root) {
if (!root) return 0;
return 1 + std::max(height(root->left), height(root->right));
}
bool isBalancedNaive(TreeNode* root) {
if (!root) return true;
int diff = std::abs(height(root->left) - height(root->right));
return diff <= 1 && isBalancedNaive(root->left) && isBalancedNaive(root->right);
}
// O(n) — оптимальный подход: возвращаем -1 как "несбалансировано"
int checkHeight(TreeNode* root) {
if (!root) return 0;
int left = checkHeight(root->left);
if (left == -1) return -1;
int right = checkHeight(root->right);
if (right == -1) return -1;
if (std::abs(left - right) > 1) return -1;
return 1 + std::max(left, right);
}
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
int main() {
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* balanced = new TreeNode(1);
balanced->left = new TreeNode(2);
balanced->right = new TreeNode(3);
balanced->left->left = new TreeNode(4);
balanced->left->right = new TreeNode(5);
assert( isBalanced(balanced));
// 1
// /
// 2
// \
// 3
TreeNode* unbalanced = new TreeNode(1);
unbalanced->left = new TreeNode(2);
unbalanced->left->right = new TreeNode(3);
assert(!isBalanced(unbalanced));
assert( isBalanced(nullptr));
}Сравнение подходов
| Подход | Время | Память | Заметки |
|---|---|---|---|
| Наивный (отдельная высота) | O(n²) | O(h) | Понятен, но медленен |
| Sentinel (-1) | O(n) | O(h) | Предпочтительный |
Оба используют O(h) стека вызовов (h — высота дерева).
Оглавление
