Объясняем условие «на пальцах»
🌲 Что такое бинарное дерево?
Представь семейное древо, но у каждого человека может быть максимум два ребёнка:
- 👈 Левый ребёнок
- 👉 Правый ребёнок
Каждый кружочек — это узел с числом внутри.
Что такое «обход» (traversal)?
Обход — это правило, по которому мы «гуляем» по дереву и записываем числа в определённом порядке.
Три главных способа обхода:
Суть задачи:
Тебе дали корень бинарного дерева. Нужно обойти его inorder (левый → корень → правый) и вернуть список чисел в порядке посещения.
⚠️ Важно: Если у узла нет левого или правого ребёнка — просто пропускаем эту часть!
🎮 Пример «на пальцах»
Пример 1: root = [1,null,2,3]
Пример 2: root = [5,3,8,1,4,null,9]
Бонус-факт: Для бинарного дерева поиска (BST) inorder-обход всегда возвращает числа в отсортированном порядке!
Как думать, как программист?
Ключевая идея: Рекурсия — это «волшебный лифт»
Представь, что у тебя есть инструкция, которую ты даёшь каждому узлу:
📜 Инструкция для узла:
1. Если есть левый ребёнок — отправь его выполнять эту же инструкцию 🔄
2. Запиши своё число в список 📝
3. Если есть правый ребёнок — отправь его выполнять эту же инструкцию 🔄
Решение №1: Рекурсия (самое простое)
Решение №2: Итеративное (со стеком)
Зачем? Иногда рекурсия может переполнить стек при очень глубоких деревьях. Итеративный подход использует явный стек (как рюкзак, куда складываем узлы).
Заключение
Примеры, рассмотренные в статье можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/tree/main/src/main/java/info/shkryl/task94_binaryTreeInorderTraversal