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

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

📝 Идея
▫️Используем два указателя: slow передвигаем на 1 позицию вперед, fast — на две
▫️Теперь, когда знаем их точку пересечения — запускаем новый указатель с начала массива и также передвигаем на одну позицию одновременно со slow
▫️Данный алгоритм всегда будет указывать на элемент, в котором образуется цикл

#solution287

🔴 Hard
23. Merge k Sorted Lists

📃 Вам дан массив k связанных списков lists, где каждый отсортирован в порядке возрастания.

Объединить все связанные списки в один отсортированный связанный список и вернуть его.

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

38/200
#hard
#leetcode23

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

Time: O(nlog(k))
Space: O(1)

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

#solution23

🔴 Hard
25. Reverse Nodes in k-Group

📃 Дан связанный список, переставьте узлы списка и верните измененный список

Правила перестановки:
Дано число k - меньшее или равное длине связанного списка, переверните узлы связанного списка через каждые k узлов
Если число узлов не кратно k, то оставшиеся узлы оставьте такими, какие они есть.

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

39/200
#hard
#leetcode25

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

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

📝 Идея
▫️Функцией getKNode проходим k узлов вперед
▫️Далее используем алгоритм переворачивания списка, но изначальной ссылкой на предыдущей элемент делаем KNode
▫️Также используем две переменные groupPrev и groupNext для сохранения нужных ссылок на части списка

#solution25

Класс TreeNode:

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

🟢 Easy
226. Invert Binary Tree

📃 Дан root - корень двоичного дерева, инвертируйте его и верните root

Подсказка: используйте рекурсию

40/200
#easy
#leetcode226

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

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

📝 Идея
▫️Заменяем ссылку на левую ветвь — ссылкой на правую, затем рекурсией делаем тоже самое для оставшихся узлов

#solution226

🟢 Easy
543. Diameter of Binary Tree

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

Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь необязательно проходит через root

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

41/200
#easy
#leetcode543

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

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

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

#solution543

🟢 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