[Leetcode 230] - Kth Smallest Element in a BST w/ Python

 

 

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed)

of all the values of the nodes in the tree.

 

 

이진 탐색 트리가 주어졌을때 트리에서 k 번째 작은 숫자를 리턴하는 문제

 

 

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

 

 

 

---

 

 

 

 

Example 1:

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

 

 

 

Example 2:

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

 

 

 

 

---

 

 

 

 

이진 탐색 트리인 만큼 중위 순회를 통해 배열에 값을 담는다면 k 번째로 작은 숫자를 구하는게 쉽다고 생각했다

 

 

중위 순회는

1. 왼쪽 노드

2. 루트 노드

3. 오른쪽 노드

 

 

로 확인을 하는데 탐색 트리에서 이를 inorder traversal 이라고 하는 만큼

가장 낮은 숫자부터 큰 값까지 순회하는것을 볼 수 있다

 

 

 

class Solution:
    def kthSmallest(self, root, k):
        ans = []

        def inOrder(root):
            if root:
                inOrder(root.left)
                ans.append(root.val)
                inOrder(root.right)
    
        inOrder(root)

        return ans[k - 1]