Задача итератор бинарного дерева

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

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

Решение:

class BSTIterator(object):

    def __init__(self, root):
        # get the in order tree node values
        def inorder(root):
            if not root:    return []
            return inorder(root.left) + [root.val] + inorder(root.right)
        
        self.treenodes = inorder(root)
        
        
    def next(self):
        # pop out the current smallest int
        return self.treenodes.pop(0)
        

    def hasNext(self):
        # check if there are remaining int
        return len(self.treenodes) != 0