✅ Решение задачи 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

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

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

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

#solution46

🟡 Medium
39. Combination Sum

📃 Учитывая массив различных целых чисел и значение target, вернуть список всех уникальных комбинаций (в любом порядке), где выбранные числа в сумме дают target.

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

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

53/200
#medium
#leetcode39

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

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

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

#solution39

🟡 Medium
90. Subsets II

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

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

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

54/200
#medium
#leetcode90

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

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

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

#solution90

🟡 Medium
79. Word Search

📃 Дана сетка символов и слово word, вернуть true, если word существует в сетке.

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

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

55/200
#medium
#leetcode79

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

Time: O(mn4^L)
Space: O(L)

📝 Идея
▫️Проходимся по сетке и используем каждый символ, как возможное начало слова
▫️Функция dfs рекурсивно реализует поиск следующего символа в слове, проверяя все ячейки вокруг текущей позиции
▫️Пометка board[i][j] = '*' необходима для того, чтобы не использовать один символ дважды

#solution79

🟡 Medium
40. Combination Sum II

📃 Дан целочисленный массив и значение target, вернуть все уникальные комбинации, в которых сумма чисел составляет target.

Каждое число может быть использовано в комбинации только один раз.

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

56/200
#medium
#leetcode40

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

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

📝 Идея
▫️Перебираем все возможные варианты, используя рекурсию и удаляя затем последний элемент
▫️Так как массив отсортирован, можно легко избежать повторяющихся комбинаций, делая проверку на равенство значений предыдущего и текущего элементов
▫️При этом условие i > start позволяет брать дублирующиеся значения в рекурсивном вызове для составления всех вариантов
▫️Стоит отметить, что прерывание цикла после выполнения условия (nums[i] > target) ускоряет код в 2 раза

#solution40