使用JavaScript Generator实现二叉搜索树中序迭代器报错求助

错误原因 #

• 第一处是笔误：在_getGen生成器函数中，递归调用右子树生成器时，你把方法名_getGen错写为了_genGen，这导致调用时返回undefined，而yield*要求后面必须跟随可迭代对象，因此直接抛出类型错误。
• 第二处是hasNext方法逻辑错误：每次调用hasNext时你直接执行了this._gen.next()，这会消耗迭代器的产出值，导致后续调用next()时会跳过当前节点值，而且返回值也写反了：done为true代表没有下一个值，所以hasNext应该返回!done才对。

正确实现方案 #

我们通过预存下一个迭代结果的方式，避免判断是否存在下一个值时消耗迭代器，修正后代码如下：

class BSTIterator {
    constructor(root) {
        this._gen = this._getGen(root);
        // 预取下一个迭代结果缓存，避免重复消耗迭代器
        this._cachedNext = this._gen.next();
    }
    
    *_getGen(node) {
        if (node) {
            yield* this._getGen(node.left);
            yield node.val;
            yield* this._getGen(node.right);
        }
    }
    
    next() {
        const currentValue = this._cachedNext.value;
        // 取完当前值后，预取下一个结果缓存
        this._cachedNext = this._gen.next();
        return currentValue;
    }
    
    hasNext() {
        // 直接读取缓存的迭代结果判断，不消耗迭代器
        return !this._cachedNext.done;
    }
}

内容的提问来源于stack exchange，提问作者Joji