Условие задачи

Имеется бинарное дерево поиска, где каждый узел содержит целочисленное значение. Необходимо найти k-ое наименьшее значение, которое содержится в узлах дерева. Важно учитывать, что индексация начинается с 1.

Примеры

Пример 1:

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

Объяснение: Корень дерева имеет значение 3. Левый потомок, узел со значением 1, является наименьшим значением. Его индекс 1, что соответствует k. Следовательно, ответ - 1.

Пример 2:

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

Объяснение: Корень дерева имеет значение 5. Левый поддерево содержит узлы со значениями 2, 3 и 4. Так как k = 3, ответом будет 3.

Решение

1. Создадим пустой список, где будут храниться значения узлов дерева.
2. Создадим функцию inorder, которая будет рекурсивно проходить по дереву и добавлять значения узлов в созданный список.
3. Выведем k-ый элемент списка.

Объяснение с примером

Для бинарного дерева [5,3,6,2,4,null,null,1] и k = 3, список значений узлов будет иметь вид [1, 2, 3, 4, 5, 6]. Значение, соответствующее третьему индексу списка, равно 3, что и является ответом.

Код на Python

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        nodes = []

        def inorder(node):
            if node:
                inorder(node.left)
                nodes.append(node.val)
                inorder(node.right)

        inorder(root)
        return nodes[k-1]