173. 二叉搜索树迭代器（JS实现）

àì夳堔傛蜴生んèń 2023-03-06 05:50 1阅读 0赞

## 1 题目 ##

> 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。  
> 调用 next() 将返回二叉搜索树中的下一个最小的数。  
> 示例：  
> BSTIterator iterator = new BSTIterator(root);  
> iterator.next(); // 返回 3  
> iterator.next(); // 返回 7  
> iterator.hasNext(); // 返回 true  
> iterator.next(); // 返回 9  
> iterator.hasNext(); // 返回 true  
> iterator.next(); // 返回 15  
> iterator.hasNext(); // 返回 true  
> iterator.next(); // 返回 20  
> iterator.hasNext(); // 返回 false  
> 提示：  
> next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。  
> 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

链接：https://leetcode-cn.com/problems/binary-search-tree-iterator

## 2 思路 ##

**这道题思路就是一个中序遍历，用一个栈来保存部分遍历的结果，先遍历左分支，将结果压入栈中，再转到右分支遍历**

## 3代码 ##

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root */
    var BSTIterator = function(root) { 
        this.root = root;
        this.stack = [];
        while(root) { 
            this.stack.push(root);
            root = root.left;
        }
    };
    
    /** * @return the next smallest number * @return {number} */
    BSTIterator.prototype.next = function() { 
        let p = this.stack.pop();
        let q = p.right;
        while(q) { 
            this.stack.push(q);
            q = q.left;
        }
        return p.val;
    };
    
    /** * @return whether we have a next smallest number * @return {boolean} */
    BSTIterator.prototype.hasNext = function() { 
        return this.stack.length > 0;
    };
    
    /** * 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() */