JavaScript: использование генератора для создания двоичного дерева поиска в порядке Итератора

Question

Я пытаюсь решить этот вопрос с leetcode https://leetcode.com/problems/binary-search-tree-iterator/, где он просит вас сделать итерацию для прохождения BST, и я подумал, что генераторы подходят для этого.

Вот моя попытка

      
class BSTIterator {
    constructor(root) {
        this.root = root
        this._gen = this._getGen(root)
    }
    
    *_getGen(node) {
        if(node) {
            yield* this._getGen(node.left)
            yield node.val
            yield* this._genGen(node.right)    
        } 
    }
    
    
    next() {
        return this._gen.next().value
    }
    
    hasNext() {
        return this._gen.next().done
    }
}

Но я получил сообщение об ошибке

      TypeError: yield* is not a terable

Может ли кто-нибудь помочь мне понять, где я ошибся и каковы правильные решения этой проблемы с помощью генераторов?

Answer 1

Несколько вопросов:

• Опечатка в yield* this._genGen(node.right)... измените его на get с t.
• будет иметь логическое значение, противоположное тому, что hasNext должен вернуться, поэтому вам нужно отрицать это
• Вы только знаете, что done когда уже сделал .next()вызвать итератор. Поэтому вам нужно, чтобы итератор всегда был на шаг впереди и запомнил возвращаемое значение в состоянии вашего экземпляра.

Итак, вот как вы можете изменить свой код:

      class BSTIterator {
    constructor(root) {
        this.root = root;
        this._gen = this._getGen(root);
        // Already call `next()`, and retain the returned value
        this.state = this._gen.next();
    }
    
    *_getGen(node) {
        if (node) {
            yield* this._getGen(node.left);
            yield node.val;
            yield* this._getGen(node.right); // fix typo
        } 
    }
    
    next() {
        let {value} = this.state; // This has the value to return
        this.state = this._gen.next(); // Already fetch next
        return value;
    }
    
    hasNext() {
        // Get `done` from the value already retrieved, and invert:
        return !this.state.done;
    }
}

Answer 2

Создайте нормальную функцию генератора, которая выдает значения в желаемом порядке, например

      function* bst(node) {
    if (node) {
        yield* bst(node.left)
        yield node.val
        yield* bst(node.right)
    }
}

Затем превратите эту функцию в «пошаговую» функцию, которая предварительно выбирает одно значение из генератора и предоставляет next/hasNext:

      function step(gen) {
    let curr = gen.next()

    return {
        next() {
            let c = curr
            curr = gen.next()
            return c.value
        },
        hasNext() {
            return !curr.done
        }
    }
}

Теперь вы можете повторять bst в стиле C++:

      for (let it = step(bst(someTree)); it.hasNext(); )
    console.log(it.next())