Задания для самостоятельного выполнения

Склонируйте репозиторий.

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

В итоге у вас должны быть следующие части практики:

  1. Код, проходящий тесты из репозитория.
  2. Код своего варианта задачи.
  3. Тесты для него.

Варианты заданий

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