Итератор бинарного дерева

Сложность: Средняя

Условие задачи: Вам нужно реализовать класс 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

🔗 Решение

Пишите свое решение в комментариях👇

@python_job_interview