[LeetCode] Python - 230. Kth Smallest Element in a BST

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

Kth Smallest Element in a BST - LeetCode

생각

BST는 왼쪽 자식노드는 루트노드보다 작고, 오른쪽 자식노드는 루트노드보다 큰 노드들로 이루어진 트리입니다. (일반화하면, 왼쪽 서브트리 < 루트 노드 < 오른쪽 서브트리)

 

그렇기 때문에, BST를 왼쪽 서브트리 탐색 -> 루트 노드 -> 오른쪽 서브트리 탐색 이 순서대로 진행하여 배열로 값을 담아내면 k번째 노드값을 찾을 수 있습니다. 이때 탐색을 시도하는 재귀함수의 기저조건은 노드가 없을 경우이므로 이 기저조건만 잘 생각하면 됩니다.

 

(Discuss에 보면 스택으로 푸는 경우도 많았는데 저는 재귀로 푸는게 더 직관적이라 이렇게 풀었습니다)

 

Python Code

# 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: TreeNode, k: int) -> int:
        ans = []
        
        def traversal(root):
            nonlocal ans
            
            if not root:
                return
            
            traversal(root.left)
            ans.append(root.val)
            traversal(root.right)
        
        traversal(root)
        
        return ans[k-1]