[LeetCode]Kth Smallest Element in BST

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 Binary Search Tree에서 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:
        output = []

        def dfs(root):
            if not root:
                return
            
            dfs(root.left)
            
            if len(output) >= k:
                return

            output.append(root.val)
            dfs(root.right)

        dfs(root)

        return output[-1]

접근 방법

1. DFS를 활용해 트리를 탐색합니다.
2. Binary Search Tree의 특성을 이용해 중위 순회합니다.
   1. BST의 경우 왼쪽 자식 - 부모 - 오른쪽 자식 순서대로 값이 증가합니다.
   2. 중위 순회역시 왼쪽 자식 - 부모 -오른쪽 자식 순서대로 탐색하기 때문에 k번째로 작은수를 찾을 수 있습니다.
   3. 중위 순회를 진행하면서 output에 담긴 갯수가 k보다 같거나 크면 함수를 종료합니다.
   4. output의 마지막 요소가 k번째로 작은 요소가 됩니다.

BST 특성과 중위 순회의 특성이 k번째로 작은 요소를 구할 수 있는 힌트가 되기 때문에 중위 순회를 응용했습니다.