LeetCode / Binary Search Tree / 173번 / Binary Search Tree Iterator / JS

< 문제 바로가기 >

Binary Search Tree Iterator - LeetCode

 

< 문제 간단설명 >

이진 탐색 트리를 전위순회를 하였을 때, 다음 노드를 반환하는 next()와 다음 노드가 존재하는지 반환하는 hasNext()를 직접 구현하는 문제이다.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 */
var BSTIterator = function (root) {
  this.queue = [];
  this.index = 0;
  this.node = root;

  const traverse = (node) => {
    if (node === null) {
      return null;
    }

    // 전위 순회
    traverse(node.left);
    this.queue.push(node);
    traverse(node.right);
  };

  traverse(root);
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function () {
  // node에 현재 index의 다음 index가 가리키는 값을 저장하고,
  // index += 1
  this.node = this.queue[this.index++];
  // 현재 노드의 값을 반환
  return this.node.val;
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function () {
  // 현재 가리키는 인덱스가 맨 끝이 아니라면 true
  return this.index !== 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()
 */