LeetCode 95. 不同的二叉搜索树 II

题意与示例

完整题目见官方页面（链接在文末）。每棵树在测试里用 LeetCode 的层序数组表示（null 表示空位，末尾多余的 null 去掉），结果按集合比较。基准解是与递归分解完全不同的方式：枚举 1 到 n 的每个排列，按顺序把数逐个插入一棵空的二叉搜索树，把形状不同的树收集下来。一共 7 组用例，n 从 1 到 7：

真实实测 · 本机执行输出

输入 [1]
输出 [[1]]
输入 [2]
输出 [[1,null,2],[2,1]]
输入 [3]
输出 [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
输入 [4]
输出 [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
输入 [5]
输出 [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
输入 [6]
输出 [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

树的个数是卡特兰数

我用同一个函数生成了 n 从 1 到 9 的所有树，检查了树的个数是否等于卡特兰数 C(2n, n) / (n + 1)，并且检查这些树的序列化结果是否互不相同：

真实实测 · 本机执行输出

n | 树的个数（solve）| 卡特兰数 C(2n,n)/(n+1) | 生成耗时（三次中最快，含序列化）
1 |        1（互不相同 1）|        1 |     0.00 ms
2 |        2（互不相同 2）|        2 |     0.00 ms
3 |        5（互不相同 5）|        5 |     0.01 ms
4 |       14（互不相同 14）|       14 |     0.02 ms
5 |       42（互不相同 42）|       42 |     0.07 ms
6 |      132（互不相同 132）|      132 |     0.24 ms
7 |      429（互不相同 429）|      429 |     0.95 ms
8 |     1430（互不相同 1430）|     1430 |     3.82 ms
9 |     4862（互不相同 4862）|     4862 |    14.18 ms

每个 n 上树的个数都严格等于卡特兰数（n = 3 时 5 棵，n = 4 时 14 棵，n = 9 时 4862 棵），并且序列化之后互不相同，没有重复的结构。生成耗时随个数快速增长，n = 9 时 14.2ms（含序列化）。

一个有趣的事实：结点是共用的

递归分解里，同一个区间 [lo, hi] 的子树列表会被很多棵树共用（不同的根会重复使用同一个子问题的结果）。因为结果里的树只需要读，直接共用同一个子树对象是安全的，不用深拷贝。我统计了实际创建的结点对象数和逐棵树展开后的结点总数：

真实实测 · 本机执行输出

同一个子树对象被多棵树共用：实际创建的结点数 vs 把每棵树都展开后的结点总数
n=4: 14 棵树，实际创建的结点对象 55 个，逐棵展开共 56 个结点
n=6: 132 棵树，实际创建的结点对象 726 个，逐棵展开共 792 个结点
n=8: 1430 棵树，实际创建的结点对象 9620 个，逐棵展开共 11440 个结点

n = 8 时一共有 1430 棵树，逐棵展开共 11440 个结点，但实际只创建了 9620 个结点对象，省下了约 16%；n = 4 时省得很少（55 个对象对 56 个结点），n = 6 时 726 个对 792 个。这个统计只在本文的解法上测得，对 n 更大的情形节省的比例还会增加，这里没有再往上测。

递归分解：五种语言的实现

build(lo, hi) 返回用 lo 到 hi 能组成的所有二叉搜索树：区间为空时返回只含"空树"的列表；否则枚举根 root 从 lo 到 hi，对左边区间的每棵树 left 和右边区间的每棵树 right，创建一个以 root 为根、left 和 right 为子树的新结点。n 为 0 时按题目返回空列表。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；测试程序把返回的树序列化成层序数组再比较（序列化代码不属于解法本身）。

Python · 解法代码class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def generate_trees(n): def build(lo, hi): # 用 lo..hi 这些数能组成的所有二叉搜索树 if lo > hi: return [None] # 区间为空：只有"空树"这一种 res = [] for root in range(lo, hi + 1): # 枚举根结点 root：左子树用 lo..root-1，右子树用 root+1..hi for left in build(lo, root - 1): for right in build(root + 1, hi): # 左右子树的每一种组合，都能配上这个根 res.append(TreeNode(root, left, right)) return res return build(1, n) if n else []

真实实测 · Python · 前几组用例的输出

$ python3 solution.py   # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON
[1]  →  [[1]]
[2]  →  [[1,null,2],[2,1]]
[3]  →  [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
[4]  →  [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
[5]  →  [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
[6]  →  [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

Java · 解法代码class TreeNode { int val; TreeNode left, right; TreeNode(int v, TreeNode l, TreeNode r) { val = v; left = l; right = r; } } class Solution { public List<TreeNode> generateTrees(int n) { return n == 0 ? new ArrayList<>() : build(1, n); } private List<TreeNode> build(int lo, int hi) { // 用 lo..hi 这些数能组成的所有二叉搜索树 List<TreeNode> res = new ArrayList<>(); if (lo > hi) { res.add(null); // 区间为空：只有"空树"这一种 return res; } for (int root = lo; root <= hi; root++) { // 枚举根结点 root：左子树用 lo..root-1，右子树用 root+1..hi for (TreeNode left : build(lo, root - 1)) { for (TreeNode right : build(root + 1, hi)) { // 左右子树的每一种组合，都能配上这个根 res.add(new TreeNode(root, left, right)); } } } return res; } }

真实实测 · Java · 前几组用例的输出

$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl
[1]  →  [[1]]
[2]  →  [[1,null,2],[2,1]]
[3]  →  [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
[4]  →  [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
[5]  →  [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
[6]  →  [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

Go · 解法代码type TreeNode struct { Val int Left, Right *TreeNode } func generateTrees(n int) []*TreeNode { var build func(lo, hi int) []*TreeNode // 用 lo..hi 这些数能组成的所有二叉搜索树 build = func(lo, hi int) []*TreeNode { if lo > hi { return []*TreeNode{nil} // 区间为空：只有"空树"这一种 } res := []*TreeNode{} for root := lo; root <= hi; root++ { // 枚举根结点 root：左子树用 lo..root-1，右子树用 root+1..hi for _, left := range build(lo, root-1) { for _, right := range build(root+1, hi) { // 左右子树的每一种组合，都能配上这个根 res = append(res, &TreeNode{Val: root, Left: left, Right: right}) } } } return res } if n == 0 { return []*TreeNode{} } return build(1, n) }

真实实测 · Go · 前几组用例的输出

$ go build -o bin . && ./bin < cases.jsonl
[1]  →  [[1]]
[2]  →  [[1,null,2],[2,1]]
[3]  →  [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
[4]  →  [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
[5]  →  [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
[6]  →  [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

JavaScript · 解法代码class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } } function generateTrees(n) { const build = (lo, hi) => { // 用 lo..hi 这些数能组成的所有二叉搜索树 if (lo > hi) return [null]; // 区间为空：只有"空树"这一种 const res = []; for (let root = lo; root <= hi; root++) { // 枚举根结点 root：左子树用 lo..root-1，右子树用 root+1..hi for (const left of build(lo, root - 1)) { for (const right of build(root + 1, hi)) { // 左右子树的每一种组合，都能配上这个根 res.push(new TreeNode(root, left, right)); } } } return res; }; return n === 0 ? [] : build(1, n); }

真实实测 · JavaScript · 前几组用例的输出

$ node run.js < cases.jsonl
[1]  →  [[1]]
[2]  →  [[1,null,2],[2,1]]
[3]  →  [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
[4]  →  [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
[5]  →  [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
[6]  →  [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

C++ · 解法代码#include <vector> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v, TreeNode* l, TreeNode* r) : val(v), left(l), right(r) {} }; class Solution { vector<TreeNode*> build(int lo, int hi) { // 用 lo..hi 这些数能组成的所有二叉搜索树 if (lo > hi) return {nullptr}; // 区间为空：只有"空树"这一种 vector<TreeNode*> res; for (int root = lo; root <= hi; root++) { // 枚举根结点 root：左子树用 lo..root-1，右子树用 root+1..hi for (TreeNode* left : build(lo, root - 1)) for (TreeNode* right : build(root + 1, hi)) // 左右子树的每一种组合，都能配上这个根 res.push_back(new TreeNode(root, left, right)); } return res; } public: vector<TreeNode*> generateTrees(int n) { if (n == 0) return {}; return build(1, n); } };

真实实测 · C++ · 前几组用例的输出

$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl
[1]  →  [[1]]
[2]  →  [[1,null,2],[2,1]]
[3]  →  [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
[4]  →  [[1,null,2,null,3,null,4],[1,null,2,null,4,3],[1,null,3,2,4],[1,null,4,2,null,null,3],[1,null,4,3,null,2],[2,1,3,null,null,null,4],[2,1,4,null,null,3],[3,1,4,null,2],[3,2,4,1],[4,1,null,null,2,null,3],[4,1,null,null,3,2],[4,2,null,1,3],[4,3,null,1,null,null,2],[4,3,null,2,null,1]]
[5]  →  [[1,null,2,null,3,null,4,null,5],[1,null,2,null,3,null,5,4],[1,null,2,null,4,3,5],[1,null,2,null,5,3,null,null,4],[1,null,2,null,5,4,null,3],[1,null,3,2,4,null,null,null,5],[1,null,3,2,5,null,null,4],[1,null,4,2,5,null,3],[1,null,4,3,5,2],[1,null,5,2,null,null,3,null,4],[1,null,5,2,null,null,4,3],[1,null,5,3,null,2,4],[1,null,5,4,null,2,null,null,3],[1,null,5,4,null,3,null,2],[2,1,3,null,null,null,4,null,5],[2,1,3,null,null,null,5,4],[2,1,4,null,null,3,5],[2,1,5,null,null,3,null,null,4],[2,1,5,null,null,4,null,3],[3,1,4,null,2,null,5],[3,1,5,null,2,4],[3,2,4,1,null,null,5],[3,2,5,1,null,4],[4,1,5,null,2,null,null,null,3],[4,1,5,null,3,null,null,2],[4,2,5,1,3],[4,3,5,1,null,null,null,null,2],[4,3,5,2,null,null,null,1],[5,1,null,null,2,null,3,null,4],[5,1,null,null,2,null,4,3],[5,1,null,null,3,2,4],[5,1,null,null,4,2,null,null,3],[5,1,null,null,4,3,null,2],[5,2,null,1,3,null,null,null,4],[5,2,null,1,4,null,null,3],[5,3,null,1,4,null,2],[5,3,null,2,4,1],[5,4,null,1,null,null,2,null,3],[5,4,null,1,null,null,3,2],[5,4,null,2,null,1,3],[5,4,null,3,null,1,null,null,2],[5,4,null,3,null,2,null,1]]
[6]  →  [[1,null,2,null,3,null,4,null,5,null,6],[1,null,2,null,3,null,4,null,6,5],[1,null,2,null,3,null,5,4,6],[1,null,2,null,3,null,6,4,null,null,5],[1,null,2,null,3,null,6,5,null,4],[1,null,2,null,4,3,5,null,null,null,6],[1,null,2,null,4,3,6,null,null,5],[1,null,2,null,5,3,6,null,4],[1,null,2,null,5,4,6,3],[1,null,2,null,6,3,null,null,4,null,5],[1,null,2,null,6,3,null,null,5,4],[1,null,2,null,6,4,null,3,5],[1,null,2,null,6,5,null,3,null,null,4],[1,null,2,null,6,5,null,4,null,3],[1,null,3,2,4,null,null,null,5,null,6],[1,null,3,2,4,null,null,null,6,5],[1,null,3,2,5,null,null,4,6],[1,null,3,2,6,null,null,4,null,null,5],[1,null,3,2,6,null,null,5,null,4],[1,null,4,2,5,null,3,null,6],[1,null,4,2,6,null,3,5],[1,null,4,3,5,2,null,null,6],[1,null,4,3,6,2,null,5],[1,null,5,2,6,null,3,null,null,null,4],[1,null,5,2,6,null,4,null,null,3],[1,null,5,3,6,2,4],[1,null,5,4,6,2,null,null,null,null,3],[1,null,5,4,6,3,null,null,null,2],[1,null,6,2,null,null,3,null,4,null,5],[1,null,6,2,null,null,3,null,5,4],[1,null,6,2,null,null,4,3,5],[1,null,6,2,null,null,5,3,null,null,4],[1,null,6,2,null,null,5,4,null,3],[1,null,6,3,null,2,4,null,null,null,5],[1,null,6,3,null,2,5,null,null,4],[1,null,6,4,null,2,5,null,3],[1,null,6,4,null,3,5,2],[1,null,6,5,null,2,null,null,3,null,4],[1,null,6,5,null,2,null,null,4,3],[1,null,6,5,null,3,null,2,4],[1,null,6,5,null,4,null,2,null,null,3],[1,null,6,5,null,4,null,3,null,2],[2,1,3,null,null,null,4,null,5,null,6],[2,1,3,null,null,null,4,null,6,5],[2,1,3,null,null,null,5,4,6],[2,1,3,null,null,null,6,4,null,null,5],[2,1,3,null,null,null,6,5,null,4],[2,1,4,null,null,3,5,null,null,null,6],[2,1,4,null,null,3,6,null,null,5],[2,1,5,null,null,3,6,null,4],[2,1,5,null,null,4,6,3],[2,1,6,null,null,3,null,null,4,null,5],[2,1,6,null,null,3,null,null,5,4],[2,1,6,null,null,4,null,3,5],[2,1,6,null,null,5,null,3,null,null,4],[2,1,6,null,null,5,null,4,null,3],[3,1,4,null,2,null,5,null,null,null,6],[3,1,4,null,2,null,6,null,null,5],[3,1,5,null,2,4,6],[3,1,6,null,2,4,null,null,null,null,5],[3,1,6,null,2,5,null,null,null,4],[3,2,4,1,null,null,5,null,null,null,6],[3,2,4,1,null,null,6,null,null,5],[3,2,5,1,null,4,6],[3,2,6,1,null,4,null,null,null,null,5],[3,2,6,1,null,5,null,null,null,4],[4,1,5,null,2,null,6,null,3],[4,1,6,null,2,5,null,null,3],[4,1,5,null,3,null,6,2],[4,1,6,null,3,5,null,2],[4,2,5,1,3,null,6],[4,2,6,1,3,5],[4,3,5,1,null,null,6,null,2],[4,3,6,1,null,5,null,null,2],[4,3,5,2,null,null,6,1],[4,3,6,2,null,5,null,1],[5,1,6,null,2,null,null,null,3,null,4],[5,1,6,null,2,null,null,null,4,3],[5,1,6,null,3,null,null,2,4],[5,1,6,null,4,null,null,2,null,null,3],[5,1,6,null,4,null,null,3,null,2],[5,2,6,1,3,null,null,null,null,null,4],[5,2,6,1,4,null,null,null,null,3],[5,3,6,1,4,null,null,null,2],[5,3,6,2,4,null,null,1],[5,4,6,1,null,null,null,null,2,null,3],[5,4,6,1,null,null,null,null,3,2],[5,4,6,2,null,null,null,1,3],[5,4,6,3,null,null,null,1,null,null,2],[5,4,6,3,null,null,null,2,null,1],[6,1,null,null,2,null,3,null,4,null,5],[6,1,null,null,2,null,3,null,5,4],[6,1,null,null,2,null,4,3,5],[6,1,null,null,2,null,5,3,null,null,4],[6,1,null,null,2,null,5,4,null,3],[6,1,null,null,3,2,4,null,null,null,5],[6,1,null,null,3,2,5,null,null,4],[6,1,null,null,4,2,5,null,3],[6,1,null,null,4,3,5,2],[6,1,null,null,5,2,null,null,3,null,4],[6,1,null,null,5,2,null,null,4,3],[6,1,null,null,5,3,null,2,4],[6,1,null,null,5,4,null,2,null,null,3],[6,1,null,null,5,4,null,3,null,2],[6,2,null,1,3,null,null,null,4,null,5],[6,2,null,1,3,null,null,null,5,4],[6,2,null,1,4,null,null,3,5],[6,2,null,1,5,null,null,3,null,null,4],[6,2,null,1,5,null,null,4,null,3],[6,3,null,1,4,null,2,null,5],[6,3,null,1,5,null,2,4],[6,3,null,2,4,1,null,null,5],[6,3,null,2,5,1,null,4],[6,4,null,1,5,null,2,null,null,null,3],[6,4,null,1,5,null,3,null,null,2],[6,4,null,2,5,1,3],[6,4,null,3,5,1,null,null,null,null,2],[6,4,null,3,5,2,null,null,null,1],[6,5,null,1,null,null,2,null,3,null,4],[6,5,null,1,null,null,2,null,4,3],[6,5,null,1,null,null,3,2,4],[6,5,null,1,null,null,4,2,null,null,3],[6,5,null,1,null,null,4,3,null,2],[6,5,null,2,null,1,3,null,null,null,4],[6,5,null,2,null,1,4,null,null,3],[6,5,null,3,null,1,4,null,2],[6,5,null,3,null,2,4,1],[6,5,null,4,null,1,null,null,2,null,3],[6,5,null,4,null,1,null,null,3,2],[6,5,null,4,null,2,null,1,3],[6,5,null,4,null,3,null,1,null,null,2],[6,5,null,4,null,3,null,2,null,1]]

真实实测 · 本机执行输出

共 7 组用例（含边界），以暴力解的结果为基准逐组比对：
  Python      通过 7/7
  Java        通过 7/7
  Go          通过 7/7
  JavaScript  通过 7/7
  C++         通过 7/7

耗时实测

n 分别为 4、6、7、8，每个规模取三次中最快的一次，基准是枚举全部 n! 个排列做插入：

真实实测 · 本机执行输出

n | 暴力解 | 本文解法
         4 |     0.036 ms | 0.021 ms
         6 |     1.487 ms | 0.258 ms
         7 |    11.605 ms | 0.964 ms
         8 |   103.946 ms | 3.637 ms

n = 8 时，基准需要插入 40320 个排列，103.9ms；递归分解 3.64ms，约 28.6 倍。基准的耗时随 n 按阶乘增长（n = 6 到 8 增长约 70 倍），递归分解按卡特兰数增长（增长约 14 倍）。

随机对拍

Python 版本另外和"排列插入"做了对拍，n 取 1 到 6：

真实实测 · 本机执行输出

随机对拍 30 组（n 取 1 到 6（结果按集合比较，树用层序数组表示）），solve 与 brute 的结果全部一致。

n 只有 6 种取值，固定用例（n 从 1 到 7）已经覆盖了所有。另外四种语言只在上面 7 组固定用例上验证过。

分步演示：n = 3 的分解

下面的演示用 n = 3，共 5 棵树。缩进表示递归的深度。区间 [1, 3] 依次让 1、2、3 当根：根 = 1 时左边区间 [1, 0] 为空（1 种），右边 [2, 3] 又递归分解成 2 种，组合得 1 × 2 = 2 棵；根 = 2 时左右各 1 种，得 1 棵；根 = 3 时左边 [1, 2] 有 2 种，右边为空，得 2 棵。合计 5 棵（卡特兰数 C₃）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的树集合与 solve 的返回值一致。

不同的二叉搜索树 II：用 1 到 3 生成所有形状不同的二叉搜索树

参考与说明

官方题目页：LeetCode 95. 不同的二叉搜索树 II。本文只用自己的话概括了题意，完整约束以官方页面为准。
数据来自本机真实运行，五种语言的版本写在页脚；耗时对比只用 Python 测量。
没有覆盖：只统计个数不生成树的版本（下一题，只需要 O(n²) 的动态规划）；用记忆化缓存每个区间的结果（本文的共用子树来自递归本身，没有另加缓存）。

下一题 · LeetCode 96

不同的二叉搜索树