В прошлой статье мы уже решали задачу на поиск в BST.
Новая задача немного сложнее. Давайте решать вместе.
Ссылка на задачу: https://leetcode.com/problems/delete-node-in-a-bst
Дан корень бинарного дерева поиска (BST) и ключ.
Нужно удалить узел с этим значением и вернуть новый корень дерева.
Если такого узла нет — вернуть дерево без изменений.
Пример 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Пример 2:
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Пример 3:
Input: root = [], key = 0
Output: []
Перед тем как посмотреть решение, подумайте как бы вы решали такую задачу?
Подписывайтесь на мой канал в Телеграмм, чтобы ничего не пропустить.
Ну или на канал в VK, если хотите видеть новые статьи у себя в ленте.
🌳 Как работает удаление в BST
Удаление узла в бинарном дереве поиска делится на 3 случая:
1. У узла нет детей — просто удаляем (возвращаем None).
2. У узла один дочерний узел — возвращаем этого ребёнка.
3. У узла два дочерних узла: Находим наименьший узел в правом поддереве (in-order successor).
Копируем его значение в текущий узел.
Удаляем этот минимальный узел из правого поддерева.
🧠 Решение на Python
📖 Идея:
- Рекурсивно ищем нужный узел.
- Обрабатываем один из трёх случаев.
- Используем вспомогательную функцию getMin для поиска минимального узла.
✅ Код:
📌 Сложность
- Время: O(h), где h — высота дерева (в среднем O(log n), в худшем O(n)).
- Память: O(h) из-за рекурсии.
Как будто достаточно быстро:
Спасибо, что дочитали до конца 🙌
Подписывайтесь на мой канал в Телеграм или VK — впереди ещё много интересного про алгоритмы, Python и LeetCode! 💡
До встречи в следующих статьях!