不同的二叉搜索树 II
在 LeetCode 上查看 ↗题目描述
给你一个整数 n，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树。可以按 任意顺序 返回答案。
示例 1
示例 2
模拟答题者思考
1. 暴力想法：枚举所有 n 个节点的二叉树形态，再检查是否 BST 且节点值为 1..n——思路对，但形态数是指数级，n=8 也会爆炸。
2. 重复在哪里？很多形态在「根选错」后仍会继续枚举左右子树，而 BST 要求左子树全部小于根、右子树全部大于根，值域天然被切开。
3. 关键转化：在闭区间 [start,end] 上选根 i，则左子树只能从 [start,i-1] 生成、右子树只能从 [i+1,end] 生成——子问题与父问题同构，用递归（或记忆化）即可。
4. 空子树也要占位：当 start > end 时返回 [None]，否则无法把「只有左子树」或「只有右子树」的情况拼进答案（例如 n=3 时根为 1 的树）。
5. 手推 n=3：根为 2 时左只有 {1}、右只有 {3}，得到唯一树 2,1,3；根为 1 时要枚举左空 × 右 [2,3] 的两种 BST，共凑出 5 棵，与卡特兰数一致。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
start / end | int | 定义：当前子树允许使用的节点值闭区间 [start, end]维护：BST 性质要求左子树值 < 根 < 右子树，故选根 i 后左区间为 [start, i-1]、右区间为 [i+1, end]更新：顶层调用 build(1, n)；每轮根候选 i 遍历 start..end |
i | int | 定义：本轮作为子树根节点的值 维护：根值一旦确定，左右子树只能在其值域两侧递归生成 更新： for i in range(start, end+1) 枚举所有可能根 |
lefts / rights | list<TreeNode?> | 定义：左（右）子树在对应区间上能生成的所有 BST 根节点列表 维护：空区间返回 [None]，表示「空子树」也要参与拼接更新： lefts = build(start, i-1)，rights = build(i+1, end) |
trees | list<TreeNode> | 定义：区间 [start,end] 上所有合法 BST 的根集合维护：对每个根 i，将 lefts 与 rights 做笛卡尔积，新建 TreeNode(i, l, r)更新：双重循环拼接后返回；顶层即为 generateTrees 的答案 |
落码步骤
1. 定义 build(start, end)：若 start > end，返回 [None]（空子树占位）
2. 初始化 trees = []，对 i 从 start 到 end 枚举根节点值
3. lefts = build(start, i-1)，rights = build(i+1, end)
4. 双重循环：对每个 l in lefts、r in rights，trees.append(TreeNode(i, l, r))
5. 返回 trees；generateTrees(n) 调用 build(1, n)（n==0 时可返回 []，本题 n≥1）
代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> list[TreeNode | None]:
def build(start: int, end: int) -> list[TreeNode | None]:
if start > end:
return [None]
trees: list[TreeNode | None] = []
for i in range(start, end + 1):
lefts = build(start, i - 1)
rights = build(i + 1, end)
for left in lefts:
for right in rights:
trees.append(TreeNode(i, left, right))
return trees
if n == 0:
return []
return build(1, n)/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return build(1, n);
}
private:
vector<TreeNode*> build(int start, int end) {
vector<TreeNode*> trees;
if (start > end) {
trees.push_back(nullptr);
return trees;
}
for (int i = start; i <= end; ++i) {
auto lefts = build(start, i - 1);
auto rights = build(i + 1, end);
for (TreeNode* left : lefts) {
for (TreeNode* right : rights) {
trees.push_back(new TreeNode(i, left, right));
}
}
}
return trees;
}
};
// 时间：与输出树棵数同阶；空间 O(n) 递归栈复杂度分析
O(4^n / n^(3/2))（与卡特兰数同阶的树枚举；n≤8 时输出规模可控）
O(n)（递归深度，不计输出树节点）
常见坑
空区间返回空列表 []：拼接时内层循环不会执行，会丢掉「只有左子树或只有右子树」的合法 BST；必须返回 [nullptr] / [None]。
根值写错：节点值就是枚举的 i（在 1..n 内），不要另建映射数组；区间 [start,end] 已经保证值互异且有序。
误以为要先算 #96「不同 BST 的个数」再构造：本题要输出所有树，必须做左右子树列表的笛卡尔积拼接，不能只计数。
必测边界 Case
n = 1 → 一棵只有根 1 的树
n = 2 → 2 棵：根 1（右子 2）或根 2（左子 1）
n = 3 → 5 棵（与示例 1 一致，可用纸笔核对根 1/2/3 三种分支）
n = 8（提示上限），树棵数为卡特兰数 C8=1430，注意输出体积而非算法常数