二叉搜索树迭代器 (opens new window)

• 难度：Medium
• 标签：

刷题思路

• [x] 提前计算法
• [ ] xx

方法 1 提前计算法

/**
 * @param {TreeNode} root
 */
var BSTIterator = function(root) {
    this.queue = []
    const stack = [root]
    while (stack.length !== 0) {
        const node = stack.pop()
        if (node.flag) {
            this.queue.push(node.val)
        } else {
            if (node.right) stack.push(node.right)
            node.flag = true
            stack.push(node)
            if (node.left) stack.push(node.left)
        }
    }
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function() {
    return this.queue.shift()
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function() {
    return this.queue.length
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */

方法 2

• 复杂度：
  • 时间 O()
  • 空间 O()

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~