[LeetCode] 230. Kth Smallest Element in a BST 문제 및 풀이 코드

문제

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

BST가 주어졌을 때 K번째로 작은 수를 찾아라.

---

코드

BST 문제의 경우 우선 순회를 어떤 식으로 할지 정해야 한다.

순회의 방식에는 inorder(left->root->right), postorder(left->rightt->root), preorder(root->left->right) 세가지의 경우가 있다.

이 문제에서는 K번째 수를 찾으라 했으니 순회를 했을때 정렬이 되는 방법을 택하는 게 좋을 듯 하다. 따라서 inorder를 택했다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
    
        return inorder(root)[k - 1]
        

---