Итератор по двоичному поисковому дереву II

Источник: https://leetcode.com/problems/binary-search-tree-iterator-ii/

Заимплементировать класс BSTIterator который представляет собой in-order обход (левое поддерево - текущий узел - правое поддерево) бинарного поискового дерева (BST):

• BSTIterator(TreeNode root) конструктор. Корень root является входным значением для конструктора.
• boolean hasNext() возвращает true если можно перейти вправо, иначе false.
• int next() перемещает указатель вправо и возвращает значение вершины.
  
• boolean hasPrev() возвращает true если можно перейти влево, иначе false.
• int prev() перемещает указатель влево и возвращает значение вершины.

После инициализации курсор указывает на несуществующее значение, то есть можно сделать next() и получить наименьший элемент в дереве.

Можем считать, чтоnext() и prev() всегда валидны. То есть когда мы их вызваем, то всегда возвращаем какое-то значение.

Пример:

Дано
["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"]
[[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]]
Результат
[null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]

Объяснение
// Подчеркнутый элемент показывает текущее положение указателя итератора
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // проинициализировали:   [3, 7, 9, 15, 20]
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 3
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 7
bSTIterator.prev(); // статус [3, 7, 9, 15, 20], return 3
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 7
bSTIterator.hasNext(); // return true
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 9
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 15
bSTIterator.next(); // статус [3, 7, 9, 15, 20], return 20
bSTIterator.hasNext(); // return false
bSTIterator.hasPrev(); // return true
bSTIterator.prev(); // статус [3, 7, 9, 15, 20], return 15
bSTIterator.prev(); // статус [3, 7, 9, 15, 20], return 9

Ограничения:

• Количество вершин в дереве находится в диапазоне [1, 105].
• 0 <= Node.val <= 106
• Не более 105 вызовов   hasNext, next, hasPrev, и prev может быть сделано.

Имплементация

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
   
// делаем двусвязный список через пойнтеры
    private class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
    }
    
    // dummy element
    ListNode iterator = null;
    
    public BSTIterator(TreeNode root) {
        List<Integer> list = dfs(root);
// посчитали массив чисел, теперь увяжем его в двусвязный список
        iterator = new ListNode();
        ListNode prev = iterator;
        for (Integer elem : list) {
            ListNode node = new ListNode();
            node.val = elem;
            prev.next = node;
            node.prev = prev;
            prev = node;
        }
        iterator.next.prev=null;
    }
   
    // in-order = идем слева, текущая вершина, идем справа
    private List<Integer> dfs(TreeNode node) {
        if (node == null) return new ArrayList<Integer>();
        List<Integer> left = dfs(node.left);
        List<Integer> right = dfs(node.right);
        left.add(node.val); // к списку слева добавляем корень поддерева
        left.addAll(right); // добавлем список справа
        return left;
    }
    
    public boolean hasNext() {
        return iterator.next!=null;
    }
    
    public int next() {
        iterator = iterator.next;
        return  iterator.val;
    }
    
    public boolean hasPrev() {
        return iterator.prev!=null;
    }
    
    public int prev() {
        iterator = iterator.prev;
        return  iterator.val;
    }
}