JavaScript: 使用Generator制作二叉搜索树In order Iterator

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。
done 将具有与 hasNext 应该 return 相反的布尔值，因此您需要否定
只有在对迭代器进行了 .next() 调用后，您才会知道 done 是什么。因此，您需要迭代器始终领先一步，并在您的实例状态中记住它的 return 值。

下面是更改代码的方法：

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;
    }
}

JavaScript: 使用Generator制作二叉搜索树In order Iterator

JavaScript: using Generator to make Binary Search Tree In order Iterator

javascript

ecmascript-6

binary-search-tree

es6-generator