现已上线！2025 年 Telegram 研究 — 年度关键洞察 
C/C++ | LeetCode
前往频道在 Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
显示更多3 256
订阅者
+124 小时
+17 天
-830 天
帖子存档
3 256
Задача: 1506. Find Root of N-Ary Tree
Сложность: medium
Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.
Верните корень N-арного дерева.
Пример:
Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.class Solution {
public:
Node* findRoot(vector<Node*> tree) {
unordered_set<int> seen;
for (Node* node : tree) {
for (Node* child : node->children) {
seen.insert(child->val);
}
}
Node* root = nullptr;
for (Node* node : tree) {
if (seen.find(node->val) == seen.end()) {
root = node;
break;
}
}
return root;
}
};3 256
Стань партнером Edler.pro и зарабатывай от 500 000 ₽/мес
✅ Продавай и внедряй решения по автоматизации найма и обучения сотрудников.
💰 Зарабатывай от 100 000 до 750 000 ₽ с каждого клиента
Стартовый бюджет: от 200 000 ₽
Окупаемость: 14 дней ⚡
Узнать больше
#реклама 16+
edler.pro
О рекламодателе
3 256
Задача: 1016. Binary String With Substrings Representing 1 To N
Сложность: medium
Если задана двоичная строка s и положительное целое число n, верните true, если двоичное представление всех целых чисел в диапазоне [1, n] является подстрокой s, или false в противном случае. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "0110", n = 3 Output: true👨💻 Алгоритм: 1⃣Генерация двоичных строк: Для каждого числа в диапазоне [1, n] сгенерируйте его двоичное представление. 2⃣Проверка подстрок: Проверьте, является ли каждое из двоичных представлений подстрокой строки s. 3⃣Возврат результата: Если все двоичные представления являются подстроками строки s, верните true. В противном случае, верните false. 😎 Решение:
class Solution {
public:
bool queryString(string s, int n) {
for (int i = 1; i <= n; ++i) {
string binary = bitset<32>(i).to_string();
binary.erase(0, binary.find_first_not_of('0'));
if (s.find(binary) == string::npos) {
return false;
}
}
return true;
}
};3 256
Получи грант на обучение в Центральном университете
Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе.
Для школьников 10-х и 11-х классов, СПО.
Подать заявку
#реклама
apply.centraluniversity.ru
О рекламодателе
3 256
Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium
Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.
Пример:
Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]👨💻 Алгоритм: 1⃣Инициализация переменных и функций: Создайте класс узла дерева TreeNode с атрибутами val, left и right. Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder. 2⃣Рекурсивная функция для построения дерева: Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева. Если текущий индекс выходит за границы массива preorder, верните null. Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null. 3⃣Создание узла и рекурсивное построение поддеревьев: Создайте новый узел с текущим значением и увеличьте индекс. Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла). Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла). Верните созданный узел. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int index = 0;
TreeNode* bstFromPreorder(vector<int>& preorder) {
return constructBST(preorder, INT_MIN, INT_MAX);
}
TreeNode* constructBST(vector<int>& preorder, int lower, int upper) {
if (index == preorder.size()) {
return NULL;
}
int val = preorder[index];
if (val < lower || val > upper) {
return NULL;
}
index++;
TreeNode* root = new TreeNode(val);
root.left = constructBST(preorder, lower, val);
root.right = constructBST(preorder, val, upper);
return root;
}
};3 256
Получи грант до 1,2 млн руб. на обучение в магистратуре
Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой?
Поступай в магистратуру Центрального университета!
- 4 офлайн программы по востребованным направлениям ИТ
- Онлайн-программа по машинному обучению
- 300 мест с грантами до 1,2 млн руб.
- Вечерние занятия и учеба по выходным — удобно совмещать с работой
- Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса
- Возможность стажировок и трудоустройства в ведущих компаниях
- Государственный диплом за 2 года
Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии.
Оставляй заявку на грант уже сейчас!
Подать заявку
#реклама 16+
apply.centraluniversity.ru
О рекламодателе
3 256
Задача: 636. Exclusive Time of Functions
Сложность: medium
На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.
Пример:
Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] Output: [3,4]👨💻 Алгоритм: 1⃣Парсинг логов: Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой. 2⃣Использование стека: Используйте стек для отслеживания текущих вызовов функций. Если лог содержит start, добавьте функцию в стек и начните отсчет времени. Если лог содержит end, снимите функцию со стека и обновите эксклюзивное время. 3⃣Обновление времени выполнения: Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций. 😎 Решение:
class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
stack<int> stack;
vector<int> times(n, 0);
int prevTime = 0;
for (const string& log : logs) {
stringstream ss(log);
string fidStr, type, timeStr;
getline(ss, fidStr, ':');
getline(ss, type, ':');
getline(ss, timeStr, ':');
int fid = stoi(fidStr);
int time = stoi(timeStr);
if (type == "start") {
if (!stack.empty()) {
times[stack.top()] += time - prevTime;
}
stack.push(fid);
prevTime = time;
} else {
times[stack.top()] += time - prevTime + 1;
stack.pop();
prevTime = time + 1;
}
}
return times;
}
};3 256
VK Weekend Offer для бэкенд-разработчиков
28–29 июня VK проведёт Weekend Offer для бэкендеров с опытом от трёх лет. Участников со знанием Java, Go, Python или C++ ждут технические собеседования, знакомство с продуктами и, если всё сложится, офер уже в конце выходных.
Ребята много лет создают облачные решения, системы рекомендаций и поисковые движки — всё с миллионами пользователей в проде — и сейчас ищут новых коллег. Поэтому оставляйте заявку до 25 июня, чтобы попасть в команду за выходные!
Подробности — на сайте.
Подать заявку
#реклама 16+
team.vk.company
О рекламодателе
3 256
Задача: 305. Number of Islands II
Сложность: hard
Дан пустой двумерный бинарный массив
grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]
class UnionFind {
vector<int> parent, rank; int count;
public:
UnionFind(int size) : parent(size, -1), rank(size, 0), count(0) {}
void addLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
bool isLand(int x) { return parent[x] >= 0; }
int numberOfIslands() { return count; }
int find(int x) { return parent[x] != x ? parent[x] = find(parent[x]) : x; }
void unionSet(int x, int y) { int xset = find(x), yset = find(y);
if (xset != yset) { if (rank[xset] < rank[yset]) parent[xset] = yset;
else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
UnionFind dsu(m * n); vector<int> answer;
vector<int> x = {-1, 1, 0, 0}, y = {0, 0, -1, 1};
for (auto& pos : positions) {
int land = pos[03 256
20 000 баллов на сервисы Яндекс Go для бизнеса
Подключайтесь к сервису и оптимизируйте бизнес-процессы без бумажной волокиты.
Яндекс Go для бизнеса как личный помощник:
- организует командировку;
- отвезет до работы;
- накормит сотрудников.
Пока вы экономите время и силы.
Узнать больше
#реклама 16+
business.go.yandex
О рекламодателе
Реклама на Яндексе
3 256
Задача: 480. Sliding Window Median
Сложность: hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000] Explanation: Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6👨💻 Алгоритм: 1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента. 2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна. 3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления. 😎 Решение:
#include <vector>
#include <algorithm>
std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
std::vector<double> medians;
for (int i = 0; i + k <= nums.size(); i++) {
std::vector<int> window(nums.begin() + i, nums.begin() + i + k);
std::sort(window.begin(), window.end());
if (k % 2 == 1) {
medians.push_back(window[k / 2]);
} else {
medians.push_back((window[k / 2 - 1] + window[k / 2]) / 2.0);
}
}
return medians;
}3 256
Профессия «Аналитик данных» - начни учиться бесплатно!
Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством.
Excel, SQL, PowerBI, Python.
Преимущества обучения в Академии Eduson:
🎓 можно начать учиться бесплатно, если не понравится — не платите
🎓 официальный государственный диплом
🎓 рассрочка 0% на 24 мес.
🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются
🎓 личный куратор с Вами на связи
Начните обучаться онлайн и получать стабильный доход уже во время обучения!
Подать заявку
#реклама 16+
eduson.academy
О рекламодателе
3 256
Задача: 179. Largest Number
Сложность: medium
Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.
Поскольку результат может быть очень большим, необходимо вернуть строку вместо целого числа.
Пример:
Input: nums = [10,2] Output: "210"👨💻 Алгоритм: 1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк по убыванию, используя компаратор, сравнивающий a + b и b + a. 2⃣Проверка на нули: Если после сортировки первый элемент равен "0", вернуть "0", так как все элементы — нули. 3⃣Формирование результата: Сконкатенировать отсортированные строки и вернуть результат. 😎 Решение:
cppКопироватьРедактироватьclass Solution {
public:
string largestNumber(vector<int> &nums) {
vector<string> strNums(nums.size());
for (int i = 0; i < nums.size(); ++i) {
strNums[i] = to_string(nums[i]);
}
sort(strNums.begin(), strNums.end(),
[](string &a, string &b) { return a + b > b + a; });
if (strNums[0] == "0") {
return "0";
}
string largestNumberStr;
for (string numAsStr : strNums) {
largestNumberStr += numAsStr;
}
return largestNumberStr;
}
};3 256
Профессия «Аналитик данных». Рассрочка 0%
Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством.
Excel, SQL, PowerBI, Python.
Преимущества обучения в Академии Eduson:
🎓 официальный государственный диплом
🎓если после курса не найдёте работу — мы возвращаем деньги и это зафиксировано в договоре
🎓 рассрочка 0% на 24 мес., то есть без переплаты
🎓 бессрочный доступ к лекциям и материалам, которые продолжают обновляться
🎓 личный куратор с Вами на связи
Начните обучаться онлайн и получать стабильный доход уже во время обучения!
Узнать больше
Финансовые услуги оказывает: ПАО "Сбербанк", АО "Тинькофф Банк" и др..
#реклама 16+
eduson.academy
О рекламодателе
3 256
Задача: 73. Set Matrix Zeroes
Сложность: medium
Дана матрица m x n, нужно обнулить всю строку и столбец, если хотя бы один элемент равен 0.
Решение должно быть на месте, без использования дополнительной матрицы.
Пример:
Input: [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]👨💻 Алгоритм: 1⃣Обход всей матрицы: Если элемент matrix[i][j] == 0, помечаем: matrix[0][j] = 0 (нужен обнулить весь столбец j) matrix[i][0] = 0 (нужен обнулить всю строку i) Первый столбец не может пересекаться с первой строкой → используем флаг isCol 2⃣Второй проход (снизу вверх, слева направо): Если matrix[i][0] == 0 или matrix[0][j] == 0, то matrix[i][j] = 0 3⃣В конце отдельно обрабатываем первую строку и первый столбец: Если matrix[0][0] == 0 → обнулить всю первую строку Если isCol == true → обнулить весь первый столбец 😎 Решение:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool isCol = false;
int R = matrix.size();
int C = matrix[0].size();
for (int i = 0; i < R; i++) {
if (matrix[i][0] == 0) {
isCol = true;
}
for (int j = 1; j < C; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (int j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (int i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
}
};3 256
Освойте профессию Системный аналитик с нуля за 7 месяцев
Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством.
Excel, BPMN, UML, Python, SQL, API
Преимущества обучения в Академии Eduson:
🎓 22 реальных бизнес-кейса
🎓 официальный государственный диплом
🎓 рассрочка 0% на 24 мес.
🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются
🎓 личный куратор с Вами на связи
Начните обучаться онлайн и получать доход уже во время обучения!
Получить скидку
#реклама 16+
eduson.academy
О рекламодателе
3 256
Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard
Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.
Пример:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
👨💻 Алгоритм:
1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.
2⃣Используйте очередь для хранения состояний игрока и коробки, а также текущего количества толчков.
3⃣Для каждого состояния проверяйте все возможные движения игрока и перемещения коробки, обновляйте очередь и отмечайте посещенные состояния.
😎 Решение:
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
auto isValid = [&](int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
};
queue<tuple<int, int, int, int, int>> q;
unordered_set<string> visited;
int px, py, bx, by, tx, ty;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'S') {
px = i;
py = j;
} else if (grid[i][j] == 'B') {
bx = i;
by = j;
} else if (grid[i][j] == 'T') {
tx = i;
ty = j;
}
}
}
q.push({px, py, bx, by, 0});
visited.insert(to_string(px) + "," + to_string(py) + "," + to_string(bx) + "," + to_string(by));
while (!q.empty()) {
auto [px, py, bx, by, pushes] = q.front();
q.pop();
if (bx == tx && by == ty) {
return pushes;
}
for (auto [dx, dy] : directions) {
int npx = px + dx, npy = py + dy;
if (isValid(npx, npy)) {
if (npx == bx && npy == by) {
int nbx = bx + dx, nby = by + dy;
if (isValid(nbx, nby) && visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(nbx) + "," + to_string(nby)).second) {
q.push({npx, npy, nbx, nby, pushes + 1});
}
} else if (visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(bx) + "," + to_string(by)).second) {
q.push({npx, npy, bx, by, pushes});
}
}
}
}
return -1;
}
};3 256
Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.
Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.
Пример:
Input: nums = [2,4,5,5,5,5,5,6,6], target = 5 Output: true Explanation: The value 5 appears 5 times and the length of the array is 9. Thus, 5 is a majority element because 5 > 9/2 is true.👨💻 Алгоритм: 1⃣Инициализация переменной count: Инициализируйте переменную count значением 0.. 2⃣Итерация по списку nums: Пройдите по каждому элементу списка nums. Если элемент num равен target, увеличьте значение переменной count. 3⃣Проверка условия мажоритарного элемента: Если count больше чем половина длины списка nums, верните true. В противном случае верните false. 😎 Решение:
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
int count = 0;
for (int num : nums) {
if (num == target) {
count++;
}
}
return count > nums.size() / 2;
}
};3 256
Получи грант на обучение в Центральном университете
Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе.
Для школьников 10-х и 11-х классов, СПО.
Подать заявку
#реклама
apply.centraluniversity.ru
О рекламодателе
3 256
Задача: 110. Balanced Binary Tree
Сложность: easy
Дано бинарное дерево. Определите, является ли оно сбалансированным по высоте.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: true👨💻 Алгоритм: 1⃣Определим функцию height, которая возвращает: -1, если узел null; 1 + max(height(left), height(right)) — в остальных случаях. 2⃣Проверим, что разность высот левого и правого поддеревьев не превышает 1. 3⃣Рекурсивно проверим, что оба поддерева также сбалансированы: если root == NULL — дерево сбалансировано (вернём true); если разность высот больше 1 — вернём false; иначе — вернём isBalanced(left) && isBalanced(right). 😎 Решение:
class Solution {
private:
int height(TreeNode* root) {
if (root == NULL) {
return -1;
}
return 1 + max(height(root->left), height(root->right));
}
public:
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
}
return abs(height(root->left) - height(root->right)) < 2 &&
isBalanced(root->left) && isBalanced(root->right);
}
};