Сегодня разберём простую, но очень полезную задачу с LeetCode — "Search in a Binary Search Tree". Она отлично подойдёт для начинающих, кто только знакомится с деревьями и рекурсией.
🧩 Условие задачи
Ссылка на задачу: https://leetcode.com/problems/search-in-a-binary-search-tree
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
На русском:
Нам дан корень бинарного дерева поиска (BST) и целое число val. Нужно найти узел, в котором значение равно val, и вернуть всё поддерево, начинающееся с этого узла. Если такого узла нет — вернуть None.
🌳 Что такое бинарное дерево поиска (BST)?
Бинарное дерево поиска — это особый вид бинарного дерева, в котором:
- Все значения в левом поддереве меньше значения текущего узла.
- Все значения в правом поддереве больше значения текущего узла.
Пример дерева:
Перед тем как посмотреть решение, подумайте как бы вы решали такую задачу?
Подписывайтесь на мой канал в Телеграмм, чтобы ничего не пропустить.
Ну или на канал в VK, если хотите видеть новые статьи у себя в ленте.
🧠 Как решать задачу?
Мы можем использовать свойства BST, чтобы эффективно искать нужное значение:
- Если текущий узел None — значит, мы ничего не нашли.
- Если root.val == val — мы нашли нужный узел, возвращаем его.
- Если val < root.val — идём в левое поддерево.
- Если val > root.val — идём в правое поддерево.
✅ Решение на Python
Вот простое и понятное рекурсивное решение:
🔍 Как работает это решение?
Допустим, мы ищем val = 2 в дереве:
- Сначала сравниваем 2 с 4. Поскольку 2 < 4, идём влево.
- Теперь сравниваем 2 с 2. Совпало! Возвращаем этот узел.
- Вместе с ним возвращается и всё поддерево: 1 и 3.
📦 Что значит "вернуть поддерево"?
В Python дерево реализовано через объекты. Если ты возвращаешь узел TreeNode, то вместе с ним возвращаются и все его потомки — левый и правый. Это и есть поддерево.
🧩 Вывод
Эта задача — отличный пример того, как можно использовать свойства бинарного дерева поиска для быстрого поиска. А ещё — это хорошая тренировка рекурсии!
Если ты только начинаешь изучать структуры данных — обязательно попробуй решить эту задачу сам.
Ну и это простое решение и есть самое быстрое. Хотя может другого и просто нет?
Спасибо, что прочли до конца 🙌
Подписывайтесь на мой канал в Телеграм или в VK — впереди ещё много интересного про ИИ, NLP и тестирование!
До встречи в следующих статьях! 💡