95. Unique Binary Search Trees II
Дано целое число 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]]
C# решение
сопоставлено/оригинал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);
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public IList<TreeNode> AllPossibleBST(
int start, int end, unordered_map<(int, int), IList<TreeNode>> memo) {
List<TreeNode> res = new List<TreeNode>();
if (start > end) {
res.push_back(null);
return res;
}
var key = (start, end);
if (memo.count(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.push_back(root);
}
}
}
memo[key] = res;
return res;
}
public IList<TreeNode> GenerateTrees(int n) {
var memo = new unordered_map<(int, int), IList<TreeNode>>();
return AllPossibleBST(1, n, memo);
}
}Java решение
сопоставлено/оригиналclass Solution {
public List<TreeNode> allPossibleBST(
int start,
int end,
Map<Pair<Integer, Integer>, List<TreeNode>> memo
) {
List<TreeNode> res = new ArrayList<>();
if (start > end) {
res.add(null);
return res;
}
if (memo.containsKey(new Pair<>(start, end))) {
return memo.get(new Pair<>(start, end));
}
for (int i = start; i <= end; ++i) {
List<TreeNode> leftSubTrees = allPossibleBST(start, i - 1, memo);
List<TreeNode> rightSubTrees = allPossibleBST(i + 1, end, memo);
for (TreeNode left : leftSubTrees) {
for (TreeNode right : rightSubTrees) {
TreeNode root = new TreeNode(i, left, right);
res.add(root);
}
}
}
memo.put(new Pair<>(start, end), res);
return res;
}
public List<TreeNode> generateTrees(int n) {
Map<Pair<Integer, Integer>, List<TreeNode>> memo = new HashMap<>();
return allPossibleBST(1, n, memo);
}
}JavaScript решение
сопоставлено/оригиналvar allPossibleBST = function (start, end, memo) {
let res = [];
if (start > end) {
res.push(null);
return res;
}
let key = start + "," + end;
if (memo[key] != undefined) {
return memo[key];
}
for (let i = start; i <= end; ++i) {
let leftSubTrees = allPossibleBST(start, i - 1, memo);
let rightSubTrees = allPossibleBST(i + 1, end, memo);
for (let j = 0; j < leftSubTrees.length; j++) {
for (let k = 0; k < rightSubTrees.length; k++) {
let root = new TreeNode(i, leftSubTrees[j], rightSubTrees[k]);
res.push(root);
}
}
}
memo[key] = res;
return res;
};
var generateTrees = function (n) {
let memo = {};
return allPossibleBST(1, n, memo);
};Python решение
сопоставлено/оригинал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)Go решение
сопоставлено/оригиналfunc allPossibleBST(
start int,
end int,
memo map[string][]*TreeNode,
) []*TreeNode {
res := []*TreeNode{}
if start > end {
res = append(res, nil)
return res
}
key := fmt.Sprintf("%d,%d", start, end)
if value, ok := memo[key]; ok {
return value
}
for i := start; i <= end; i++ {
leftSubTrees := allPossibleBST(start, i-1, memo)
rightSubTrees := allPossibleBST(i+1, end, memo)
for _, left := range leftSubTrees {
for _, right := range rightSubTrees {
root := TreeNode{Val: i, Left: left, Right: right}
res = append(res, &root)
}
}
}
memo[key] = res
return res
}
func generateTrees(n int) []*TreeNode {
memo := make(map[string][]*TreeNode)
return allPossibleBST(1, n, memo)
}Algorithm
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.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.