10,2 тыс подписчиков
Итератор бинарного дерева
Сложность: Средняя
Условие задачи: Вам нужно реализовать класс BSTIterator, представляющий из себя итератор вдоль бинарного дерева, сцепленного по правилу: левый потомок, корень, правый потомок.
Класс должен содержать в себе следующие методы:
- BSTIterator(TreeNode root). Данный метод инициализирует объект класса. root передаются в конструктор в качестве входного аргумента. Указатель должен быть инициализирован несуществующим числом, которое меньше любого из элементов бинарного дерева;
- boolean hasNext(). Возвращает true в случае если существует потомок у правого поддерева. В ином случае возвращает false;
- int next(). Перемещает указатель в правую ветвь, возвращая число в указателе.
При инициализации указатель на несуществующий наименьший элемент, вызывая метод next(), будет возвращать наименьший элемент бинарного дерева.
Пример:
Ввод:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Вывод: [null, 3, 7, true, 9, true, 15, true, 20, false]
Объяснение:
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False
🔗 Решение
Пишите свое решение в комментариях👇
1 минута
30 ноября 2023