Задача: 95. Unique Binary Search Trees II
Сложность: 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.

😎 Решение:

public class Solution {
    public IList<TreeNode> AllPossibleBST(
        int start, int end, Dictionary<(int, int), IList<TreeNode>> memo) {
        List<TreeNode> res = new List<TreeNode>();
        if (start > end) {
            res.Add(null);
            return res;
        }

        var key = (start, end);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }

        for (int i = start; i <= end; ++i) {
            IList<TreeNode> leftSubTrees = AllPossibleBST(start, i - 1, memo);
            IList<TreeNode> rightSubTrees = AllPossibleBST(i + 1, end, memo);
            foreach (TreeNode left in leftSubTrees) {
                foreach (TreeNode right in rightSubTrees) {
                    TreeNode root = new TreeNode(i, left, right);
                    res.Add(root);
                }
            }
        }

        memo[key] = res;
        return res;
    }

    public IList<TreeNode> GenerateTrees(int n) {
        var memo = new Dictionary<(int, int), IList<TreeNode>>();
        return AllPossibleBST(1, n, memo);
    }
}

Ставь 👍 и забирай 📚 Базу знаний