173-二叉搜索树迭代器.md

173-二叉搜索树迭代器

难度：中等 原题 参考

题目

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。

解法

解题思路

• 中序遍历本质上是升序遍历，借助栈的先进后出设计二叉搜索树的迭代器
• 中序遍历的迭代： 先将整棵左子树加入栈中，然后依次弹出；如果右子树不为空的话，将整棵右子树的左子树加入栈中

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 */
let stack = [];
let res = 0 ;
var BSTIterator = function(root) {
   //加入树的最左边的一条链
   while(root){
       stack.push(root);
       root = root.left;
   }
};

/**
 * @return the next smallest number
 * @return {number}
 */
// 为什么 先弹出左子树 就是最小的值呢，是因为 左子树 本身就是最小的值对不
// 看官方题目中的二叉树的图，每次左边的就是最小的值，所以应该就是 左子树 本身就是每一次循环中最小的值
BSTIterator.prototype.next = function(p) {
    //先弹出左子树
    p = stack.pop();
    //保存当前弹出的值
    res = p.val;
    //加入右子树中的最左边的一条链
    p = p.right;
    while(p){
        stack.push(p);
        p = p.left;
    }
    return res;
};

/**
 * @return whether we have a next smallest number
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function() {
   return stack.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()
 */