173. Binary Search Tree Iterator

173. Binary Search Tree Iterator

 

https://youtu.be/RXy5RzGF5wo?si=EcNVv54-gR9Tln1F

 

이 클래스는 BST를 중위 순회(in-order traversal) 순서로 순회하며, 노드 값을 반환하는 이터레이터를 구현합니다.
* in-order traversal: 중위 순회는 왼쪽 → 현재 노드 → 오른쪽 순서로 노드를 방문합니다.
클래스는 다음 두 가지 주요 메서드를 제공합니다:
next(): 이터레이터의 포인터를 다음 노드로 이동하고, 해당 노드의 값을 반환.
hasNext(): 이터레이터가 더 탐색할 노드가 있는지 확인.
next()와 hasNext()의 동작

 

DFS, 재귀로..
그러나, 제한 사항이..

• next()와 hasNext()를 평균 O(1) 시간 안에 실행하고 
• O(h) 메모리를 사용하도록 구현할 수 있나요? 
• 여기서 h는 트리의 높이입니다.

따라서, 스텍으로 구현

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []

        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        """
        next()**는 현재 포인터를 이동시켜 다음 노드의 값을 반환
            중위 순회를 따라 왼쪽에서 오른쪽으로 이동
        스텍으로 구현하므로, 다음노드는 이미 스텍에 쌓여있음.
            현재 인덱스 바로 밑의 값임
        """
        res = self.stack.pop()

        # 이때 반환 전에, 오른쪽에 노드 있으면, 
        # 오른쪽 노드의 왼쪽 밑으로 쭉.. 내려가서.A
        # 미리 추가 하고..
        cur = res.right
        while cur:
            self.stack.append(cur)
            cur = cur.left

        return res.val

    def hasNext(self) -> bool:
        """
        hasNext()는 현재 포인터 기준으로 
            더 탐색할 노드가 있으면 True, 없으면 False를 반환
        stack 으로 구현하므로, hashNext call 했을때,
            stack 이 비워있으면, 다음 탐색 노드가 없다는 의미니, False
            아니면, True
        """
        return self.stack != []  # 비어있지 않으면 True
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()