Задания для самостоятельного выполнения
Склонируйте репозиторий.
- Напишите код, который проходит тесты из репозитория - это базовый вариант.
- На его основе напишите тесты для своего варианта.
- Имея отлаженный код деревьев, проходящий все тесты, используйте его для решения задачи по своему варианту.
В итоге у вас должны быть следующие части практики:
- Код, проходящий тесты из репозитория.
- Код своего варианта задачи.
- Тесты для него.
Варианты заданий
- Дано целое число
n
. Вернуть все структурно-уникальные BST, которые имеют ровноn
узлов с уникальными значениями от1
доn
. - Дано BST, в котором значения ровно двух узлов дерева были ошибочно поменяны местами. Необходимо восстановить дерево, не изменяя его структуру.
- Дан связный список, элементы которого отсортированы по возрастанию. Необходимо преобразовать его в сбалансированное по высоте BST.
- Дано BST и целое число
k
. Необходимо найтиk
-ый минимум среди всех значений узлов дерева. - Дано бинарное дерево поиска и два заданных узла в этом дереве. Необходимо найти наименьшего общего предка этих двух узлов в дереве.
- Реализуйте сериализацию и десериализацию BST.
- Дано BST. Необходимо преобразовать это дерево в “Greater Tree”, так что каждый ключ в исходном BST заменяется на сумму исходного ключа и всех ключей в BST, которые больше исходного ключа.
- Дано BST и два значения:
low
иhigh
. Необходимо усечь дерево так, чтобы все его элементы находились в интервале \( [ \tt{low}, \tt{high} ] \). При этом обрезка не должна изменять относительную структуру элементов, которые останутся в дереве (т.е. все потомки любого узла должны остаться потомками). Необходимо вернуть усечённое BST. Обратите внимание, что корень может измениться в зависимости от заданных границ. - Дан массив целых чисел, являющийся результатом preorder обхода BST. Необходимо построить и вернуть это дерево.
- Даны два BST
t1
иt2
. Необходимо вернуть список/массив, содержащий все значения узлов обоих деревьев, отсортированных в порядке возрастания. - Дано BST и целевое значение
v
. Необходимо разделить дерево на два поддерева, первое должно содержать узлы, которые меньше или равныv
, а второе - большеv
. Исходное дерево может не содержать узел со значением, равнымv
. Кроме того, большая часть структуры исходного дерева должна остаться неизменной. - Даны два BST и значение
target
. ВернутьTrue
, если в первом дереве есть узелn1
и во втором дереве есть узелn2
, такие что:n1.value + n2.value == target
.