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

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