🖼Иллюстрация алгоритма к задаче 4

Пример: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5,6,7]

#figure #binarysearch

➡️ Стартуем тему бинарного дерева

▫Binary Tree — это структура данных, где каждый узел имеет не более двух потомков: левого и правого.

Бинарные деревья широко используются для хранения, обработки и обхода данных, таких как выражения, файловые системы или структура HTML-страниц. Например: дерево принятия решений в игре (если "нет" — налево, если "да" — направо).

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;
    }
}

▫Binary Search Tree (BST) — бинарное дерево поиска, частный случай бинарного дерева, в котором:
➖все значения в левом поддереве меньше значения текущего узла
➖все значения в правом поддереве больше
Такое упорядочивание позволяет быстро искать, добавлять и удалять значения.

▫Основные алгоритмы обхода: BFS и DFS
🔹BFS (Breadth-First Search) — обход в ширину:
➖ проходит по дереву уровень за уровнем: сначала корень, затем все его дети, потом внуки и так далее
➖ работает с помощью очереди (queue) — узлы обрабатываются в порядке поступления
➖ пример: поиск ближайшего выхода из лабиринта — сначала проверяешь все соседние комнаты, потом комнаты за ними, постепенно расширяя круг

🔹 DFS (Depth-First Search) — обход в глубину:
➖ проходит по дереву, уходя как можно глубже по одной ветке, затем возвращается
➖реализуется через рекурсию или стек (stack) — сначала погружается, потом возвращается
➖ пример: исследование пещеры — идёшь до конца одного тоннеля, только потом возвращаешься и пробуешь следующий путь

#binarytree

📚 Про рекурсию

Рекурсия — это когда функция вызывает сама себя, чтобы решить задачу по частям.

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

▫Представь, что ты надел несколько пар носков один на другой и хочешь их снять:
➖сначала ты снимаешь верхнюю пару, потом — ещё одну, и так далее, пока не останешься босиком.
Ты повторяешь одно и то же действие, уменьшая оставшийся объём работы. При этом обязательно должно быть условие остановки, иначе будешь снимать носки вечно 😄.

▫Ближе к коду: как работает рекурсия внутри программы, как компьютер "запоминает" каждый шаг и потом возвращается назад?

Каждый раз, когда функция вызывает саму себя, программа:
➖кладет текущий шаг в стек (представь бумажку с задачей)
➖вызывает следующую функцию (ещё одна бумажка поверх)
➖так продолжается, пока программа не дойдёт до базового случая
Затем программа начинает извлекать задачи из стека, в обратном порядке, и на каждом шаге сохраняет и возвращает результат.

▫Классический пример — вычисление факториала. Каждый вызов ждёт результат следующего и только потом считает своё значение:

public static int factorial(int n) {
    if (n == 1) return 1;             // базовый случай
    return n * factorial(n - 1);      // рекурсивный шаг
}

factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * 1) = 6

#recursion

🟢Easy
101. Symmetric Tree

Company: 📕🔍📱

📝Дано двоичное дерево.

Верните true, если оно является зеркальным отражением самого себя, то есть симметричным относительно своего центра

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

#leetcode101 | #easy #binarytree

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

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

💡 Идея
🟦Чтобы понять идею симметрии в бинарном дереве, достаточно взглянуть на его структуру: каждый правый узел на одной стороне должен соответствовать левому узлу на другой стороне — и наоборот

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

🟦Создадим вспомогательную функцию helper, принимающую два узла. Сначала обрабатываем базовые случаи:
➖если оба узла равны null, значит, мы достигли конца поддеревьев синхронно — возвращаем true
➖если только один из узлов равен null, симметрия нарушена — возвращаем false
➖если значения в узлах не совпадают — также возвращаем false

🟦Если все эти проверки пройдены, рекурсивно вызываем helper для левого поддерева первого узла и правого поддерева второго, а также для правого поддерева первого и левого поддерева второго — тем самым продолжая зеркальное сравнение

👩‍💻 Java Algo | #solution101

🟢Easy
404. Sum of Left Leaves

Company: 🚔📱❤️

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

Лист — это узел без потомков. Левый лист — это лист, который является левым потомком другого узла

💡: в рекурсивную функцию добавьте "флаг" левого узла

#leetcode404 | #easy #binarytree

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