173. Binary Search Tree Iterator

Leetcode link

解题思路

题目给我们一个 BST 的根节点，要求我们写一个能够中序遍历的迭代器。

在没看到题目最后一行要求 O(1) 时间复杂度与 O(h) 空间复杂度的时候，我想的是直接一个先进先出队列加一个中序遍历搞定。

但是限制了空间复杂度之后就只能用折中的方法了：

1. 构造一个方法 particalInorder，依次保存当前节点的最左边枝干
2. 在构造函数调用上述方法
3. 然后在每次 next 执行的时候尝试用当前节点的右节点调用上述方法
4. hasNext 执行的时候只要判断保存枝干的栈是否为空就好

如此一来，保存枝干的栈就不需要一次把全部的节点都保存进去了。

C++

class BSTIterator {
 private:
  // 用来保存枝干的栈
  stack<TreeNode*> s;
  // 每次只保存最左边的枝干
  void partialInorder(TreeNode* node) {
    while (node != nullptr) {
      s.push(node);
      node = node->left;
    }
  }

 public:
  BSTIterator(TreeNode* root) { partialInorder(root); }

  int next() {
    TreeNode* res = s.top();
    s.pop();
    // 保存当前节点的右节点的左枝干
    partialInorder(res->right);
    return res->val;
  }

  bool hasNext() { return !s.empty(); }
};

Javascript

var BSTIterator = function(root) {
    this.partialInorder(root)
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function() {
    let res = this.stack.pop();
  // 保存当前节点的右节点的左枝干
    this.partialInorder(res.right);
    return res.val;
};

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

// 用来保存当前节点的左枝干
BSTIterator.prototype.partialInorder = function(node) {
    while(node) {
        this.stack.push(node);
        node = node.left;
    }
};

// 用一个栈来保存枝干
BSTIterator.prototype.stack = []