[Leetcode] 230. Kth Smallest Element in a BST (python)

#1.  문제

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

Kth Smallest Element in a BST - LeetCode

 

 

이진 탐색 트리가 주어질 때, k 번째 작은 값을 찾는 문제 (1-indexed)

Input: 
root = [5,3,6,2,4,null,null,1]
k = 3

Output: 
3

Explanation:
3이 3번째로 작다. (1-indexed)

 

---

#2.  풀이

 

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:

        def dfs(node, stack):

            # Base case
            if node is None:
                return

            # Stacking values
            stack.append(node.val)

            # Recursive
            dfs(node.left, stack)
            dfs(node.right, stack)

            # Return the stack at the end
            return stack

        stack = []

        stacked = dfs(root, stack)
        stacked.sort()

        return stacked[k-1]

 

530번 문제와 매우 유사하다.stack에 트리 값들을 적재하는 로직은 동일하며, 단순히 k번째 작은 값을 찾기만 하는 문제.최적화를 생각하지 않는다면 단순히 스택에 값을 적재하기만 하면 끝나는 문제다.