[Leetcode] 173. Binary Search Tree Iterator - JS

https://leetcode.com/problems/binary-search-tree-iterator/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
이진 검색 트리의 중위순회 반복기를 나타내는 BSTIterator 클래스 구현하라.
이진 검색 트리의 root는 제공된다.
포인터는 이진 검색 트리의 모든 요소보다 작으면서 존재하지 않는 숫자로 초기화 되어야 한다.
hasNext()는 포인터 오른쪽 순회하는 숫자가 있으면 true, 그렇지 않으면 false
next()는 포인터 오른쪽으로 이동한 뒤 이동한 곳에 위치한 숫자를 반환한다.

존재하지 않는 가장 작은 숫자에 대한 포인터를 초기화함으로써 next()에 대한 첫 번째 호출은 BST에서 가장 작은 요소를 반환합니다.
next() 호출은 항상 유효하다고 가정할 수 있습니다. 즉, next()가 호출될 때 순회에는 최소한 다음 숫자가 있게 됩니다.

제한조건
--------------------
- 노드의 갯수는 1 ~ 10^5개이다.
- 0 <= Node.val <= 10^5
- 10^5 회의 메서드 호출이 발생할 것이다.

 

2. 접근 방법

접근방법
--------------------
이진 검색 트리가 주어졌을 때, 중위순회로 배열에 담아둔다.

 

 

3. 코드

/**
 * 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.visited = [];

    const traverse = (node) => {
        if (!node) return;
        if (node.left) traverse(node.left);
        this.visited.push(node);
        if (node.right) traverse(node.right);
    }

    traverse(root)
    
};

/**
 * @return {number}
 */
BSTIterator.prototype.next = function() {
    let shifted = this.visited.shift();
    return shifted.val
};

/**
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function() {
    return this.visited.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()
 */

 

 

4. 복잡도 분석

- 시간복잡도: O(1) 

- 공간복잡도: O(n)

 

이진 검색 트리는 구현이 되어있으니 이를 중위순회로 순회하여 배열에 추가해주었다.

next 메서드는 배열의 맨 앞 요소를 제거하면 되므로 시간복잡도를 O(1)로 처리할 수 있다.

hasNext 메서드는 배열의 요소가 존재하면 다음 요소가 있는 것이므로 길이가 0보다 큰 지 비교해주었다.