[LeetCode] 230 | Kth Smallest Element in a BST | Python

---

문제 링크: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

---

문제

Given the root of a binary search tree, and an integer k, return the $k^{th}$ smallest value (1-indexed) of all the values of the nodes in the tree.

---

조건

• The number of nodes in the tree is n.
• 1 <= k <= n <= $10^4$
• 0 <= Node.val <= $10^4$

---

내 풀이

우리가 이 문제를 직접 푼다면 BST의 제일 왼쪽 끝 노드로 가서 하나씩 올라올 것이다.

이 방법을 그대로 코드로 구현한다. 그럼 iterative하게 구현될 것이다.

 

나는 smallest라는 함수로 구현했다.

[root.left로 계속 타고 내려가고, 끝에 도달하면 self.arr 리스트에 현재 val을 저장한다. 그 후에 root.right로 내려간다.]

이 과정을 반복하며 self.arr의 길이가 k가 될 때 제일 마지막에 추가된 원소를 리턴하면 된다.

왜냐하면 제일 작은 수부터 차례로 추가하고 있었기 때문이다.

---

코드

# 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 Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.arr = []
        self.k = k
        self.smallest(root, self.arr)
        
        return self.arr[-1]
        
    def smallest(self, root, arr):
        if root:
            self.smallest(root.left, arr)
        
            if len(self.arr) < self.k:
                self.arr.append(root.val)
            else:
                return

            self.smallest(root.right, self.arr)