0095. Unique Binary Search Trees II¶
题目信息¶
- 题号:
不同的二叉搜索树 II
- 难度:
Medium
- 主题:
二叉搜索树、分治、记忆化、Catalan 结构
- 原题:
- 重点:
从枚举根节点拆分值域,推导到缓存重复区间并组合左右子树
题目重述¶
给定整数 n,返回所有由数值 1..n 各使用一次构成、结构互不相同的二叉搜索树。
每棵树都必须满足:任意节点左子树中的值严格小于该节点,右子树中的值严格大于该节点。答案顺序不限。
约束为 1 <= n <= 8。
自建示例¶
输入:n = 2
输出(层序表示):[[1,null,2],[2,1]]
以 1 为根时,2 只能位于右子树;以 2 为根时,1 只能位于左子树。
输入:n = 3
输出数量:5
以 1、2、3 为根时分别产生 2、1、2 棵树,总数为 5。
C++ 实现¶
#include <vector>
class Solution {
private:
std::vector<std::vector<std::vector<TreeNode*>>> memo;
std::vector<std::vector<char>> computed;
std::vector<TreeNode*> empty_range{nullptr};
TreeNode* cloneTree(TreeNode* node) {
if (!node) {
return nullptr;
}
return new TreeNode(
node->val,
cloneTree(node->left),
cloneTree(node->right));
}
void destroyTree(TreeNode* node) {
if (!node) {
return;
}
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
std::vector<TreeNode*> directGenerate(int start, int end) {
if (start > end) {
return {nullptr};
}
std::vector<TreeNode*> result;
for (int root_value = start; root_value <= end; ++root_value) {
auto left_trees = directGenerate(start, root_value - 1);
auto right_trees = directGenerate(root_value + 1, end);
for (TreeNode* left_tree : left_trees) {
for (TreeNode* right_tree : right_trees) {
result.push_back(new TreeNode(
root_value,
cloneTree(left_tree),
cloneTree(right_tree)));
}
}
for (TreeNode* tree : left_trees) {
destroyTree(tree);
}
for (TreeNode* tree : right_trees) {
destroyTree(tree);
}
}
return result;
}
const std::vector<TreeNode*>& generateRange(int start, int end) {
if (start > end) {
return empty_range;
}
if (computed[start][end]) {
return memo[start][end];
}
computed[start][end] = true;
auto& result = memo[start][end];
for (int root_value = start; root_value <= end; ++root_value) {
const auto& left_trees = generateRange(start, root_value - 1);
const auto& right_trees = generateRange(root_value + 1, end);
for (TreeNode* left_tree : left_trees) {
for (TreeNode* right_tree : right_trees) {
result.push_back(new TreeNode(
root_value,
cloneTree(left_tree),
cloneTree(right_tree)));
}
}
}
return result;
}
std::vector<TreeNode*> memoizedGenerate(int n) {
memo.assign(
n + 2,
std::vector<std::vector<TreeNode*>>(n + 2));
computed.assign(n + 2, std::vector<char>(n + 2));
generateRange(1, n);
std::vector<TreeNode*> result = std::move(memo[1][n]);
for (int start = 1; start <= n; ++start) {
for (int end = start; end <= n; ++end) {
for (TreeNode* tree : memo[start][end]) {
destroyTree(tree);
}
}
}
return result;
}
public:
std::vector<TreeNode*> generateTrees(int n) {
return memoizedGenerate(n);
}
};
题解¶
排列建树¶
最直接的思路是枚举 1..n 的所有插入顺序,再依次插入二叉搜索树并去除重复结构。
该方法至少检查 n! 个排列,而且不同插入顺序可能得到同一棵树。它把大量时间花在重复结构上,没有利用连续值域对根节点的约束。
根节点拆分¶
考虑一个必须使用连续值域 [start, end] 的子问题。选择 root_value 作为根后,二叉搜索树性质立即确定两侧值域:
左子树使用 [start, root_value - 1]
右子树使用 [root_value + 1, end]
左右值域互不重叠。任取一棵合法左树和一棵合法右树,都能与当前根组成合法结果,因此固定根的答案是两个子树集合的笛卡尔积。
空区间¶
当 start > end 时,应返回包含一个 nullptr 的集合,而不是空集合。
nullptr 表示“这一侧没有子树”,是组合过程中的一个合法选择。若返回空集合,叶节点的左右结果数都为零,笛卡尔积将无法生成任何叶节点。
空左树集合 = {nullptr}
空右树集合 = {nullptr}
组合结果数 = 1 * 1 = 1
区间分治¶
直接分治为每个根递归生成左右区间,再枚举所有左右组合。不同根值产生不同根节点;根值相同时,不同的左树或右树组合又产生不同结构,因此结果不会重复。
任意合法 BST 都有唯一根值。该根强制划分左右值域,递归又会生成其唯一的左右结构,所以所有合法树都会被覆盖。
重复区间¶
直接分治会反复生成相同区间。例如生成 [1,4] 时,区间 [1,2] 可能从多个上层根选择再次出现。
记忆化以 (start, end) 为状态,第一次生成后保存该区间的全部树模板。后续访问同一区间直接复用模板集合,不再重复展开根节点与子区间。
独立节点¶
同一棵子树模板可能与多个另一侧模板组合。若直接把模板指针挂到多个根节点下,不同返回树会共享可变节点,修改或释放其中一棵树可能影响其他树。
实现把缓存结果视为结构模板,每次组合时深复制左右子树:
new root(root_value, clone(left_template), clone(right_template))
因此每棵生成树拥有独立节点集合。顶层缓存的所有权最终转移给返回结果,其余区间模板在返回前释放。
根值分组¶
n = 3 时,各根节点的组合数量如下:
根值 |
左区间树数 |
右区间树数 |
组合数 |
|---|---|---|---|
1 |
1 个空树 |
2 |
2 |
2 |
1 |
1 |
1 |
3 |
2 |
1 个空树 |
2 |
固定根的数量是左右结果数之积,对所有根求和正是 Catalan 递推结构。
复杂度¶
设第 n 个 Catalan 数为 C_n,它也是最终树的数量。每棵返回树包含 n 个节点,仅构造独立输出就需要 Theta(n * C_n) 时间与返回空间。
记忆化还保存较短区间的树模板,其节点总量仍为 O(n * C_n);递归深度为 O(n)。直接分治会额外重复生成相同区间,实际工作量更高。