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

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

💡 Идея
🟦Решение основано на рекурсивном обходе дерева (DFS) с передачей дополнительного логического флага isLeft, который указывает, является ли текущий узел левым ребёнком своего родителя. Это позволяет точно определить, какие листья левые и включать в сумму только их

🟦Реализуем вспомогательную функцию dfs:
➖Базовый случай — если узел null, возвращаем 0

➖Если узел — лист (нет потомков):
▫если он левый (isLeft == true), возвращаем его значение
▫иначе возвращаем 0

➖Если узел — не лист:
▫рекурсивно вызываем dfs для левого поддерева с флагом true
▫для правого поддерева — с флагом false
▫возвращаем сумму результатов обоих вызовов

👩‍💻 Java Algo | #solution404

🟢Easy
270. Closest Binary Search Tree Value

Company: 🏢📱📱

📝Дано двоичное дерево поиска (BST) и значение target.

Верните значение в BST, которое ближе всего к target. Если есть несколько ответов, верните наименьший

💡: пользуясь свойством BST, найдите для target ближайшие границы сверху и снизу

#leetcode270 | #easy #binarytree

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

Time: O(h)
Space: O(1)

💡 Идея
🟦Главное свойство BST: в левом поддереве всегда лежат меньшие значения, в правом — большие

🟦Чтобы найти значение, ближайшее к target, будем искать две границы:
➖нижнюю (low) — наибольшее значение, не превышающее target
➖верхнюю (high) — наименьшее значение, не меньшее target

🟦Пока текущий узел не равен null, сравниваем его значение с target:
➖если значение меньше target, это возможный кандидат на low, но потенциально ближе значение может быть правее
➖если значение больше или равно, это кандидат на high, но есть шанс найти более близкое значение левее

🟦Так мы обходим BST, не перебирая все узлы, а двигаясь по направлению к потенциально лучшим вариантам и запоминая текущие приближения. В конце сравниваем low и high и возвращаем то, что ближе к target

👩‍💻 Java Algo | #solution270

🟡Medium
863. All Nodes Distance K in Binary Tree

Company: 📱🚖✴️

📝Дан корень двоичного дерева, целевой узел target и целое число k.

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

💡: сохраните в HashMap ссылки на родителей для всех узлов, а затем начните обход дерева с целевого узла со счетчиком k

#leetcode863 | #medium #binarytree

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

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

💡 Идея
🟦В данной задаче легко определить узлы, находящиеся на расстоянии k от target в пределах одного поддерева (просто запускаем dfs от узла target cо счетчиком). Сложность состоит в том, чтобы найти подходящие узлы, которые находятся в других частях дерева (как 5 и 1 в примере)

🟦В стандартной структуре бинарного дерева отсутствуют ссылки на родителей, поэтому необходимо заранее построить такие связи. Для этого реализуем вспомогательную функцию addParents, которая проходит все дерево и сохраняет для каждого узла его родителя в HashMap

🟦Далее остается запустить dfs от узла target, но кроме обычных направлений к потомкам (влево и вправо), добавляем движение наверх (к родителю). На каждом шаге глубина k уменьшается, и при достижении k == 0 текущий узел добавляется в результат. Для предотвращения зацикливания используем HashSet, куда добавляем уже обработанные узлы

🟦Таким образом:
➖построение связей с родителями выполняется за O(n)
➖dfs также посещает каждый узел не более одного раза — O(n)
В итоге получаем эффективный алгоритм за O(n)

👩‍💻 Java Algo | #solution863

🟡Medium
314. Binary Tree Vertical Order Traversal

Company: 🏢🔍📱

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

Если два узла находятся в одной строке и столбце, порядок должен быть слева направо

💡: используйте обход в ширину и группируйте узлы по столбцам в HashMap

#leetcode314 | #medium #binarytree

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

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

💡 Идея
🟦Назначим корню столбец с номером 0 и теперь, двигаясь влево, уменьшаем столбец на 1, вправо – увеличиваем на 1, получая для каждого узла уникальный номер столбца. Все значения узлов группируем в HashMap, где ключ — это номер столбца, а значение — список узлов, находящихся в этом столбце

🟦Для обхода дерева используем не привычный dfs, а обход в ширину (bfs), который позволяет обрабатывать узлы уровень за уровнем, гарантируя правильный порядок сверху вниз:

В реализации bfs используем очередь Queue<Pair>, где Pair — это структура, содержащая сам узел и его номер столбца. Каждый раз, когда мы извлекаем узел из очереди, мы добавляем его значение в список соответствующего столбца в HashMap и помещаем в очередь его левого и правого детей с обновлёнными номерами столбцов.

private static class Pair {
TreeNode node;
int column;

public Pair(TreeNode node, int column) {
this.node = node;
this.column = column;
}
}

🟦После завершения обхода, HashMap содержит все значения, отсортированные по вертикальным столбцам, но правильный порядок самих столбцов не гарантирован, поэтому во время обхода отслеживаем минимальный и максимальный номер столбца (minCol и maxCol).
Это позволяет в конце пройти по столбцам от самого левого до самого правого, добавляя значения из HashMap в итоговый список в нужном порядке

👩‍💻 Java Algo | #solution314

🟡Medium
99. Recover Binary Search Tree

Company: 🔍📱📱

📝Дано двоичное дерево поиска (BST), где значения ровно двух узлов были поменяны местами по ошибке.

Восстановите дерево, вернув узлам правильные значения

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

#leetcode99 | #medium #binarytree

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

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

💡 Идея
🟦Для начала взглянем на массив [1,5,3,4,2], в котором только два элемента (2, 5) стоят не на своих местах для полностью отсортированного

🟦У данных элементов есть признак – они меньше предыдущего значения, поэтому можно использовать это свойство для поиска неверных узлов в BST, остается только правильно пройти по дереву

🟦Для этого выполняем in-order обход:
➖идём всегда к самому левому (наименьшему) узлу, по пути сохраняя узлы в стек, чтобы потом вернуться к ним

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

▫если это первое нарушение, мы сохраняем предыдущий узел как first, а текущий — как second
▫если first уже найден, то это второе нарушение, и мы обновляем только second

➖после обработки текущего узла переходим в его правое поддерево и продолжаем обход

🟦Когда весь обход завершён, достаточно поменять значения узлов first и second, чтобы восстановить правильный порядок в BST

👩‍💻 Java Algo | #solution99

🟡Medium
662. Maximum Width of Binary Tree

Company: 🔍📱🚖

📝Дано двоичное дерево, верните его максимальную ширину среди всех уровней.

Ширина уровня определяется, как длина между самым левым и самым правым ненулевыми узлами, где нулевые узлы между ними, которые присутствовали бы в полном бинарном дереве, также учитываются при расчете длины

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

#leetcode662 | #medium #binarytree

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

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

💡 Идея
🟦Для вычисления ширины каждого уровня бинарного дерева логично использовать обход в ширину (BFS). Однако простого подсчёта количества узлов на уровне недостаточно, поскольку между крайними узлами могут находиться пропущенные (null) элементы

🟦Чтобы точно учитывать структуру дерева и «пустые места», мы храним в очереди пары из узла и его индекса, как если бы дерево было полным. Индексы позволяют определить "реальное" положение узлов на уровне.
Класс Pair:

private static class Pair {
TreeNode node;
int index;

public Pair(TreeNode node, int index) {
this.node = node;
this.index = index;
}
}

🟦Пока очередь не пуста, для каждого уровня:
➖cохраняем индекс первого узла на уровне — start
➖обрабатываем все узлы текущего уровня:

▫для каждого узла обновляем текущий индекс — index
▫если у узла есть потомки, добавляем их в очередь с новыми индексами: для левого — 2 * index, для правого — 2 * index + 1

➖после обработки вычисляем ширину: index - start + 1

👩‍💻 Java Algo | #solution662

🟡Medium
687. Longest Univalue Path

Company: 📱🔍

📝Дано двоичное дерево, верните длину самого длинного пути, где каждый узел имеет одинаковое значение.

Длина пути между двумя узлами равна ​​числу ребер между ними

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

#leetcode687 | #medium #binarytree

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

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

💡 Идея
🟦Используя обход в глубину, можно посчитать длину пути с одинаковыми значениями для левого и правого поддеревьев, тогда результатом максимальной длины пути для текущего узла будет значение left + right, которое легко обновлять, используя глобальную переменную

🟦Получаем, что в каждом вызове функции dfs:
➖cразу возвращаем 0, если текущий узел равен null

➖рекурсивно вызываем функцию для левого и правого поддеревьев, передавая текущее значение, как родительское

➖далее проверяем на максимальный результат left + right

➖и в конце возвращаем результат для текущего вызова:
▫если текущее значение равно родительскому — продолжаем цепочку и возвращаем 1 + максимальное значение из left и right
▫иначе возвращаем 0

👩‍💻 Java Algo | #solution687

🟡Medium
545. Boundary of Binary Tree

Company: 📱📕🚖

📝Дано двоичное дерево, верните значения его границы.

Граница бинарного дерева представляет собой объединение:
➖корня
➖левой границы
➖листьев (узлы, не имеющие потомков), упорядоченных слева направо
➖обратной последовательности правой границы

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

#leetcode545 | #medium #binarytree

🔴Hard
968. Binary Tree Cameras

Company: 🏢🚔📱

📝Дано двоичное дерево. Верните минимальное количество камер, необходимое для наблюдения за всеми узлами дерева.

Каждая камера на узле может контролировать своего родителя, себя и своих непосредственных потомков

💡: обходите дерево снизу вверх, присваивая каждому узлу состояние: требует камеру (-1), покрыт без камеры (0), содержит камеру (1)

#leetcode968 | #hard #binarytree

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

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

💡 Идея
🟦Естественно, размещение камер на всех узлах — это лишнее, поэтому мы стремимся размещать камеры стратегически, в идеале на родителях листовых узлов, а не на самих листьях

🟦Это приводит нас к подходу снизу вверх (постпорядковый DFS) с использованием системы состояний, чтобы определить, какое действие следует предпринять на каждом уровне

🟦Реализуем функцию dfs, которая возвращает:
➖-1 — если узлу нужна камера
➖ 0 — если узел охвачен камерой
➖ 1 — если у узла есть камера

🟦Обходим дерево, используя метод обратного поиска в глубину:
➖рекурсивно вычисляем статус левого и правого поддеревьев

➖если какому-либо ребенку нужна камера (-1) , помещаем камеру в текущий узел: увеличиваем счетчик и возвращаем 1

➖если у какого-либо дочернего узла есть камера (1) , текущий узел будет покрыт — возвращаем 0

➖если оба дочерних узла покрыты и не имеют камер, то этому узлу она нужна — возвращаем -1

🟦После выполнения обхода, если корню по-прежнему нужна камера, мы увеличиваем счетчик еще раз

👩‍💻 Java Algo | #solution968

🔴Hard
272. Closest Binary Search Tree Value II

Company: 📱📱📱

📝 Дано двоичное дерево поиска (BST), значение target и целое число k.

Верните k значений в BST, которые наиболее близки к target. Вы можете вернуть ответ в любом порядке

💡: используйте in-order обход, а затем примените идею из данной задачи

#leetcode272 | #hard #binarytree

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

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

💡 Идея
🟦Решение сводится к знакомому алгоритму на нахождение k ближайших элементов с применением бинарного поиска, если собрать отсортированный список из узлов дерева

🟦Для этого необходимо пройти бинарное дерево поиска in-order:
➖рекурсивно проходим до самого левого элемента (наименьшего), затем, поднимаясь вверх по стеку рекурсии, добавляем значение узла в список и переходим к правому поддереву, продолжая обход

🟦В результате получаем отсортированный список, к которому применяем бинарный поиск для нахождения левой границы ответа:
➖если элемент mid ближе к target, чем mid + k, значит элемент mid + k, а также каждый элемент справа от него не может быть в ответе, поэтому, перемещаем правую границу

➖та же самая логика, но в обратном порядке — если элемент mid + k ближе к target, перемещаем левую границу

🟦В конце возвращаем k элементов из списка, используя найденную границу: subList(left, left + k)

👩‍💻 Java Algo | #solution272

🔴Hard
297. Serialize and Deserialize Binary Tree

Company: 🚔📱📱

📝Разработайте алгоритм сериализации и десериализации бинарного дерева. Никаких ограничений на реализацию нет.

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

Для решения реализуйте класс Codec:

public class Codec {

    public String serialize(TreeNode root) {}

    public TreeNode deserialize(String data) {}
}

💡: сериализуйте дерево, используя dfs и разделяя значения запятыми, а при десериализации рекурсивно восстанавливайте левое и правое поддеревья

#leetcode297 | #hard #binarytree