Today's Challenge

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Kth Smallest Element in a BST - LeetCode

릿코드는 트리 문제가 많이 나오는 듯 하다.

오늘도 어떻게 풀어야 할지 전혀 감이 안와서 다른 사람이 올려놓은 해설을 참고해서 소스 작성해봄.

소스 작성 및 제출 후 문제를 다시 보니 BST(Binary Search Tree)에서 k번째 작은 수를 구하는 거였음.
BST는 이미 정렬이 되어 있는 상태니까 inorder(중위 순회)로 돌면서 임시 list에 값들을 집어 넣고, k-1 인덱스의 값을 가져오면 됨.

코드는 생각보다 간단하다. 아니 당연히 간단한건가..

class Solution:
    def __init__(self):
        self.a = []  
    
    def inorder(self, root: TreeNode):
        if not root:
            return
        self.inorder(root.left)
        self.a.append(root.val)
        self.inorder(root.right)        
        
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.inorder(root)
        return self.a[k-1]