📕문제

[Leetcode] 230. Kth Smallest Element in a BST

문제 설명

BST에서 k번째로 작은 숫자를 구하는 문제다.

---

📝풀이

이전에 풀었던 98.Validate Binary Search Tree와 코드가 유사하다.
BST는 중위순회하면 오름차순이라는 점을 이용한다.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        curr = root
        prev = None
        count =  0
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            count += 1
            if count == k:
                return curr.val
            prev = curr
            curr = curr.right

• 탐색에 필요한 스택과 탐색 중 현재 노드를 저장할 변수 curr, 직전에 방문한 노드를 저장할 변수 prev를 설정한다.

1. 트리의 왼쪽 끝까지 내려가며 스택에 노드를 저장한다.
2. 스택에서 노드를 꺼내 curr값을 업데이트 하고 카운트한다.
3. 스택에서 꺼낸 노드가 k번째라면 값을 반환한다.
4. 그렇지 않으면 prev값과 curr값을 업데이트하며 탐색을 계속한다.