173. Binary search tree iterator

Answer:

  1. The binary search tree is traversed in order to output each value of the binary search tree in order.
  2. We can start by reviewing the code that uses stack assist for intermediate traversal.
var inorderTraversal = function (root) {
  let result = [];
  let stack = [];
  let curr = root;

  while (stack.length || curr) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }

    node = stack.pop();
    curr = node.right;
    result.push(node.val);
  }

  return result;
};
Copy the code
  1. Each callnext()Is equivalent to executing the command oncewhileLoop inside the code and returnnode.val.
  2. whilewhileThe judgment condition of the cycle can be taken ashasNext()The judgment method of.
/ * * *@param {TreeNode} root* /
var BSTIterator = function (root) {
  this.curr = root; // Cache the current value of the node
  this.stack = []; // Cache the node to be evaluated next time
};

/ * * *@return {number}* /
BSTIterator.prototype.next = function () {
  // It is possible to traverse to the bottom of the tree when curr is empty and there are elements in the stack.
  // It is also possible for curr to have a value and stack to be empty, such as traversing to the root of a binary tree.
  while (this.curr) {
    // Continuously traverse the nodes to the left, pushing all nodes onto the stack
    this.stack.push(this.curr);
    this.curr = this.curr.left;
  }

  // Remove the top node from the stack and read its value
  const node = this.stack.pop();
  // Assign the right child of node to curr to ensure traversal order
  this.curr = node.right;

  // Returns the value of the current node
  return node.val;
};

/ * * *@return {boolean}* /
BSTIterator.prototype.hasNext = function () {
  // The iteration ends when the stack is cleared and curr is empty
  return Boolean(this.stack.length || this.curr);
};
Copy the code