95. 不同的二叉搜索树 II
题目描述
输入整数 n。用值为 1 到 n 的 n 个节点（每个值用一次）可以搭出多种不同结构的二叉搜索树。
二叉搜索树中，每个节点左子树的值都比它小，右子树的值都比它大。
生成所有这样的树，把它们的根节点放在一个列表里返回，顺序不限。每棵树按层序写成数组，空位置用 null 表示。
示例 1
输入：n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
解释：3 个节点共能搭出 5 棵不同的二叉搜索树。
示例 2
输入：n = 1 输出：[[1]]
数据范围
1 <= n <= 8
解题思路
分治：build(lo, hi) 返回由 lo..hi 组成的所有 BST。枚举根 v，左子树必须由 lo..v-1 组成，右子树必须由 v+1..hi 组成；递归得到两侧所有可能后，两两组合挂到新的根 v 上。空区间返回 [None]，这样一侧为空时也能正常组合。
为什么正确
build(lo, hi) 返回的每棵树都恰好包含 lo..hi 的全部值，而且都是 BST，互不相同。
复杂度分析
共有卡特兰数 C(n) ≈ 4ⁿ / n^1.5 棵树，时间和空间都与输出规模同阶，约 O(n·C(n))。
易错点
空区间要返回 [None] 而不是 []，否则外层循环一次都不执行，叶子挂不上去；每次组合都要新建根节点，不能复用同一个根反复改 left 和 right。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def generateTrees(self, n):
def build(lo, hi):
if lo > hi:
return [None]
res = []
for v in range(lo, hi + 1):
for left in build(lo, v - 1):
for right in build(v + 1, hi):
res.append(TreeNode(v, left, right))
return res
return build(1, n)class Solution {
List<TreeNode> build(int lo, int hi) {
List<TreeNode> res = new ArrayList<>();
if (lo > hi) {
res.add(null);
return res;
}
for (int v = lo; v <= hi; v++) {
for (TreeNode left : build(lo, v - 1)) {
for (TreeNode right : build(v + 1, hi)) {
res.add(new TreeNode(v, left, right));
}
}
}
return res;
}
public List<TreeNode> generateTrees(int n) {
return build(1, n);
}
}class Solution {
public:
vector<TreeNode*> build(int lo, int hi) {
if (lo > hi) {
return {nullptr};
}
vector<TreeNode*> res;
for (int v = lo; v <= hi; v++) {
for (TreeNode* left : build(lo, v - 1)) {
for (TreeNode* right : build(v + 1, hi)) {
res.push_back(new TreeNode(v, left, right));
}
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
return build(1, n);
}
};func generateTrees(n int) []*TreeNode {
var build func(lo, hi int) []*TreeNode
build = func(lo, hi int) []*TreeNode {
if lo > hi {
return []*TreeNode{nil}
}
res := []*TreeNode{}
for v := lo; v <= hi; v++ {
for _, left := range build(lo, v-1) {
for _, right := range build(v+1, hi) {
res = append(res, &TreeNode{Val: v, Left: left, Right: right})
}
}
}
return res
}
return build(1, n)
}var generateTrees = function(n) {
const build = (lo, hi) => {
if (lo > hi) {
return [null];
}
const res = [];
for (let v = lo; v <= hi; v++) {
for (const left of build(lo, v - 1)) {
for (const right of build(v + 1, hi)) {
res.push(new TreeNode(v, left, right));
}
}
}
return res;
};
return build(1, n);
};function generateTrees(n: number): Array<TreeNode | null> {
const build = (lo: number, hi: number): Array<TreeNode | null> => {
if (lo > hi) {
return [null];
}
const res: Array<TreeNode | null> = [];
for (let v = lo; v <= hi; v++) {
for (const left of build(lo, v - 1)) {
for (const right of build(v + 1, hi)) {
res.push(new TreeNode(v, left, right));
}
}
}
return res;
};
return build(1, n);
}