🟢 Easy
110. Balanced Binary Tree

📃 Дано бинарное дерево, определите, является ли оно
сбалансированный по высоте.

Сбалансированное дерево — это дерево, в котором глубина двух поддеревьев каждого узла не отличается более чем на единицу.

Подсказка: используйте рекурсию, проверяя каждый узел на сбалансированность

42/200
#easy
#leetcode110

✅ Решение задачи 110

Time: O(n)
Space: O(n)

📝 Идея
▫️Используя рекурсию, доходим до конца дерева для правой и левой ветки, считая при этом глубину
▫️В каждом узле делаем проверку на сбалансированность, при этом, если одно из поддеревьев несбалансированное, также возвращаем -1, так как для положительного ответа все узлы дерева должны быть сбалансированы

#solution110

🟢 Easy
572. Subtree of Another Tree

📃 Даны корни двух двоичных деревьев root и subRoot, вернуть true, если в root существует поддерево с той же структурой и значениями узлов, как в subRoot

Поддерево бинарного дерева — это дерево, состоящее из узла и всех его потомков. Дерево также можно рассматривать как поддерево самого себя.

Подсказка: рекурсивно проверяйте каждый узел на возможное поддерево

43/200
#easy
#leetcode572

✅ Решение задачи 572

Time: O(nm)
Space: O(n)

📝 Идея
▫️Проходимся по всему дереву root и для каждого узла функцией sameTree делаем проверку на идентичность данного поддерева и subroot
▫️Функция sameTree просто проходится по обоим деревьям, сравнивая значения

#solution572

🟡 Medium
235. Lowest Common Ancestor of a Binary Search Tree

📃 Для заданного двоичного дерева найдите узел наименьшего общего предка двух заданных узлов p и q

Наименьший общий предок — ближайший узел, который имеет p и q в качестве потомков (также узел может быть потомком самого себя)

Подсказка: используйте тот факт, что слева от узла находятся значения меньше, а справа больше

44/200
#medium
#leetcode235

✅ Решение задачи 235

Time: O(log(n))
Space: O(1)

📝 Идея
▫️Поскольку для каждого узла слева находятся меньшие значения, а справа большие:
- если p и q меньше текущего узла, точно переходим влево, если больше — вправо
- если p меньше текущего узла, а q больше — значит мы нашли нужный узел

#solution235

🟡 Medium
102. Binary Tree Level Order Traversal

📃 Дан root — корень двоичного дерева, вернуть порядок обхода значений его узлов (т.е. слева направо, уровень за уровнем)

Подсказка: рекурсивно обходите дерево в ширину, сохраняя номер уровня

45/200
#medium
#leetcode102

✅ Решение задачи 102

Time: O(n)
Space: O(n)

📝 Идея
▫️Проходим по дереву, сохраняя в результат узел под текущим индексом уровня
▫️При переходе к дочерним узлам увеличиваем индекс

#solution102

🟡 Medium
199. Binary Tree Right Side View

📃 Дан root — корень двоичного дерева, представьте, что вы смотрите на него с правой стороны, верните значения узлов, которые вы видите (сверху вниз)

Подсказка: сохраняйте глубину дерева и на каждом уровне выбирайте только один узел

46/200
#medium
#leetcode199

✅ Решение задачи 199

Time: O(n)
Space: O(n)

📝 Идея
▫️Проходим по дереву и на каждом уровне выбираем только один узел, начиная с самого правого
▫️Если номер уровня совпадает с размером списка результатов, значит на этом уровне ещё ничего не добавлялось

#solution199

🟡 Medium
1448. Count Good Nodes in Binary Tree

📃 Дан root — корень двоичного дерева, узел X в дереве называется хорошим, если на пути от корня до X нет узлов со значением, большим X.
Верните количество хороших узлов

Подсказка: используйте обход в глубину, сохраняя текущий максимум

47/200
#medium
#leetcode1448

✅ Решение задачи 1448

Time: O(n)
Space: O(n)

📝 Идея
▫️Обходим дерево в глубину, поддерживая текущий максимум
▫️Если значение узла больше или равно текущему максимуму — увеличиваем количество хороших узлов

#solution1448

🟡 Medium
98. Validate Binary Search Tree

📃 Дан root — корень двоичного дерева, определите, является ли оно допустимым двоичным деревом поиска:

- левое поддерево узла содержит узлы только с меньшими значениями
- правое поддерево узла — только с большими
И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Подсказка: проходите дерево в глубину, передвигая правую и левую границу диапазона для проверки условий

48/200
#medium
#leetcode98

✅ Решение задачи 98

Time: O(n)
Space: O(n)

📝 Идея
▫️Обходите дерево в глубину и в зависимости от стороны обновляйте границы диапазона:
- для левого узла обновляем правую границу, так как все значения теперь должны быть меньше значения текущего узла
- для правого узла обновляем левую границу, так как все значения теперь должны быть больше значения текущего узла

#solution98

🟡 Medium
230. Kth Smallest Element in a BST

📃 Дан root — корень двоичного дерева поиска и целое число k. Вернуть к-ое наименьшее значение (начиная с первого) среди всех значений узлов в дереве

Подсказка: пройдите дерево в глубину так, чтобы сохранять значения по возрастанию

49/200
#medium
#leetcode230

✅ Решение задачи 230

Time: O(n)
Space: O(n)

📝 Идея
▫️Рекурсивно проходим дерево, двигаясь всегда по левой стороне
▫️Дойдя до конца дерева, т.е. до наименьшего значения, добавляем его в список и поднимаемся выше по стеку вызовов функций, двигаемся также в правый узел, собирая все наименьшие значения

#solution230

🔴 Hard
124. Binary Tree Maximum Path Sum

📃 Дан root — корень двоичного дерева, вернуть максимальную сумму, используя любой путь (узел может появляться в последовательности не более одного раза)

Подсказка: для каждого узла проверяйте возможный максимум, как сумму значения текущего узла и наибольшей суммы правого и левого поддеревьев

50/200
#hard
#leetcode124

✅ Решение задачи 124

Time: O(n)
Space: O(n)

📝 Идея
▫️Для каждого узла считаем возможный максимум, складывая значение текущего узла, посчитанную максимальную сумму в левом поддереве и в правом
▫️Максимальная сумма для каждого узла — это значение этого узла + максимум из левого и правого поддерева (для выбора оптимальной последовательности)
▫️При подсчете максимумов левого и правого поддеревьев используется сравнение с нулем, так как возможен случай отрицательной суммы

#solution124

🟡 Medium
78. Subsets

📃 Дан целочисленный массив уникальных элементов, вернуть все возможные подмножества

Набор решений не должен содержать повторяющиеся подмножества, вернуть решение можно в любом порядке

Подсказка: рекурсивно перебирайте все варианты, начиная с первого элемента

51/200
#medium
#leetcode78

✅ Решение задачи 78

Time: O(n*2^n)
Space: O(2^n)

📝 Идея
▫️Последовательно перебираем все возможные варианты с первого элемента до конца массива, запуская рекурсию с добавление следующего элемента
▫️После того, как встретился базовый случай, то есть индекс массива равен его длине — добавляем текущий подмассив в результат
▫️Затем удаляем последний элемент, чтобы использовать все возможные варианты
▫️В результате получаем следующую последовательность:
[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []

#solution78

🟡 Medium
46. Permutations

📃 Дан массив различных чисел, вернуть все возможные перестановки (в любом порядке)

Подсказка: для каждого элемента массива рекурсивно перебирайте все варианты оставшихся элементов

52/200
#medium
#leetcode46