Задача: 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.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    public function allPossibleBST($start, $end, &$memo) {
        $res = [];
        if ($start > $end) {
            $res[] = null;
            return $res;
        }
        if (array_key_exists("{$start},{$end}", $memo)) {
            return $memo["{$start},{$end}"];
        }

        for ($i = $start; $i <= $end; ++$i) {
            $leftSubTrees = $this->allPossibleBST($start, $i - 1, $memo);
            $rightSubTrees = $this->allPossibleBST($i + 1, $end, $memo);
            foreach ($leftSubTrees as $left) {
                foreach ($rightSubTrees as $right) {
                    $root = new TreeNode($i, $left, $right);
                    $res[] = $root;
                }
            }
        }

        $memo["{$start},{$end}"] = $res;
        return $res;
    }

    public function generateTrees($n) {
        $memo = [];
        return $this->allPossibleBST(1, $n, $memo);
    }
}

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