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

▫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

🟢Easy
101. Symmetric Tree

Company: 📕🔍📱

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

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

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

#leetcode101 | #easy #binarytree

🟢Easy
404. Sum of Left Leaves

Company: 🚔📱❤️

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

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

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

#leetcode404 | #easy #binarytree

🟢Easy
270. Closest Binary Search Tree Value

Company: 🏢📱📱

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

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

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

#leetcode270 | #easy #binarytree

🟡Medium
863. All Nodes Distance K in Binary Tree

Company: 📱🚖✴️

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

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

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

#leetcode863 | #medium #binarytree

🟡Medium
314. Binary Tree Vertical Order Traversal

Company: 🏢🔍📱

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

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

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

#leetcode314 | #medium #binarytree

🟡Medium
99. Recover Binary Search Tree

Company: 🔍📱📱

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

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

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

#leetcode99 | #medium #binarytree

🟡Medium
662. Maximum Width of Binary Tree

Company: 🔍📱🚖

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

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

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

#leetcode662 | #medium #binarytree

🟡Medium
687. Longest Univalue Path

Company: 📱🔍

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

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

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

#leetcode687 | #medium #binarytree

🟡Medium
545. Boundary of Binary Tree

Company: 📱📕🚖

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

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

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

#leetcode545 | #medium #binarytree

🔴Hard
968. Binary Tree Cameras

Company: 🏢🚔📱

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

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

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

#leetcode968 | #hard #binarytree