Сложность: medium
Дано целое число n. Верните все структурно уникальные деревья бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Ответ может быть представлен в любом порядке.
Пример:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
👨💻 Алгоритм:
1️⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее:
2️⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)].
3️⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res.
😎 Решение:
class Solution:
def allPossibleBST(self, start, end, memo):
res = []
if start > end:
res.append(None)
return res
if (start, end) in memo:
return memo[(start, end)]
for i in range(start, end + 1):
leftSubTrees = self.allPossibleBST(start, i - 1, memo)
rightSubTrees = self.allPossibleBST(i + 1, end, memo)
for left in leftSubTrees:
for right in rightSubTrees:
root = TreeNode(i, left, right)
res.append(root)
memo[(start, end)] = res
return res
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
memo = {}
return self.allPossibleBST(1, n, memo)
Ставь 👍 и забирай 📚 Базу знаний