京公网安备11010502063487号给定整数 n，问用 1 到 n 这 n 个互不相同的数，能组成多少种结构不同的二叉搜索树。上一题（第 95 题）要把每一棵树都造出来，这一题只要数出个数，所以不需要真的建树。二叉搜索树的结构由"选谁当根"决定：如果选第 root 小的数当根，那么比它小的 root - 1 个数必须在左子树，比它大的 n - root 个数必须在右子树，左右两边互相独立，方案数相乘。用 dp[k] 表示 k 个结点能组成的树的个数，dp[k] 等于对 root 从 1 到 k 求 dp[root-1] × dp[k-root] 的和。这个数列就是卡特兰数。本文用真实运行验证它与卡特兰数公式一致，展示不带记忆化递归的调用次数，用 Java 展示 n = 20 时 32 位整数溢出，给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。n 不超过 19（这样答案在 32 位有符号整数范围内）。基准解是卡特兰数的通项公式 C(2n, n) / (n + 1)，与用递推填表是完全不同的两条路。一共 12 组用例，n 取 1 到 8、10、15、18、19：
输入 [1] 输出 1 输入 [2] 输出 2 输入 [3] 输出 5 输入 [4] 输出 14 输入 [5] 输出 42 输入 [6] 输出 132
按定义写的递归：f(n) = Σ f(i-1) × f(n-i)，同一个 f(k) 会被反复计算很多次。下面是真实统计的递归调用次数：
不带记忆化的递归：调用次数与耗时 n= 5: 结果 42，递归调用 135 次， 0.02 ms；动态规划只有 15 次乘加 n= 8: 结果 1430，递归调用 3645 次， 0.56 ms；动态规划只有 36 次乘加 n=10: 结果 16796，递归调用 32805 次， 3.95 ms；动态规划只有 55 次乘加 n=12: 结果 208012，递归调用 295245 次， 39.97 ms；动态规划只有 78 次乘加
n = 5、8、10、12 时，调用次数是 135、3645、32805、295245，n 每增加 1 大约乘 3，是指数增长；动态规划只需要约 n²/2 次乘加（n = 12 时 78 次）。
题目把 n 限制在 19，原因是 f(19) = 1767263190 刚好在 32 位有符号整数的范围内（最大 2147483647），f(20) 就超出了。下面是真实运行的 Java 程序，对比 int 和 long：
Java：用 int 和 long 分别计算（题目限制 n ≤ 19）： n=19 int: 1767263190 long: 1767263190 n=20 int: -2025814172 long: 6564120420
n = 19 时两者一致；n = 20 时 int 得到 -2025814172（溢出回绕成了负数），long 得到正确的 6564120420。所以如果要把这道题推广到更大的 n，必须换更宽的整数类型。
dp[0] = 1（空树也算一种）。对 k 从 1 到 n，对 root 从 1 到 k：dp[k] += dp[root - 1] * dp[k - root]。返回 dp[n]。时间 O(n²)，空间 O(n)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(n): dp = [0] * (n + 1) # dp[k]：k 个不同的数能组成多少种二叉搜索树 dp[0] = 1 # 0 个结点：只有一种（空树） for k in range(1, n + 1): for root in range(1, k + 1): # 选第 root 小的数当根：左子树有 root-1 个结点，右子树有 k-root 个 dp[k] += dp[root - 1] * dp[k - root] return dp[n]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [1] → 1 [2] → 2 [3] → 5 [4] → 14 [5] → 42 [6] → 132
Java · 解法代码class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; // dp[k]：k 个不同的数能组成多少种二叉搜索树 dp[0] = 1; // 0 个结点：只有一种（空树） for (int k = 1; k <= n; k++) for (int root = 1; root <= k; root++) // 选第 root 小的数当根：左子树 root-1 个结点，右子树 k-root 个 dp[k] += dp[root - 1] * dp[k - root]; return dp[n]; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [1] → 1 [2] → 2 [3] → 5 [4] → 14 [5] → 42 [6] → 132
Go · 解法代码func numTrees(n int) int { dp := make([]int, n+1) // dp[k]：k 个不同的数能组成多少种二叉搜索树 dp[0] = 1 // 0 个结点：只有一种（空树） for k := 1; k <= n; k++ { for root := 1; root <= k; root++ { // 选第 root 小的数当根：左子树 root-1 个结点，右子树 k-root 个 dp[k] += dp[root-1] * dp[k-root] } } return dp[n] }
$ go build -o bin . && ./bin < cases.jsonl [1] → 1 [2] → 2 [3] → 5 [4] → 14 [5] → 42 [6] → 132
JavaScript · 解法代码function numTrees(n) { const dp = new Array(n + 1).fill(0); // dp[k]：k 个不同的数能组成多少种二叉搜索树 dp[0] = 1; // 0 个结点：只有一种（空树） for (let k = 1; k <= n; k++) for (let root = 1; root <= k; root++) // 选第 root 小的数当根：左子树 root-1 个结点，右子树 k-root 个 dp[k] += dp[root - 1] * dp[k - root]; return dp[n]; }
$ node run.js < cases.jsonl [1] → 1 [2] → 2 [3] → 5 [4] → 14 [5] → 42 [6] → 132
C++ · 解法代码#include <vector> using namespace std; class Solution { public: int numTrees(int n) { vector<int> dp(n + 1, 0); // dp[k]：k 个不同的数能组成多少种二叉搜索树 dp[0] = 1; // 0 个结点：只有一种（空树） for (int k = 1; k <= n; k++) for (int root = 1; root <= k; root++) // 选第 root 小的数当根：左子树 root-1 个结点，右子树 k-root 个 dp[k] += dp[root - 1] * dp[k - root]; return dp[n]; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [1] → 1 [2] → 2 [3] → 5 [4] → 14 [5] → 42 [6] → 132
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
n 分别为 100、300、1000、2000，每个规模取三次中最快的一次（Python 的整数不会溢出，所以答案会变成非常大的整数）：
n | 暴力解 | 本文解法
100 | 0.005 ms | 0.362 ms
300 | 0.019 ms | 5.032 ms
1000 | 0.115 ms | 275.123 ms
2000 | 0.432 ms | 4049.855 ms在 Python 里，直接用公式（基准）比动态规划快得多：n = 2000 时 0.432ms 对 4049.9ms。原因有两个：公式是 C 实现的一次大整数运算；动态规划的 O(n²) 次乘加，在 n 大时每次都是对上千位大整数的运算，所以耗时比 n² 增长得更快（n 从 300 到 1000，耗时增长约 55 倍，n² 只有 11 倍）。这不影响本题的正确性，题目限制 n ≤ 19，动态规划远远够用；这里只是说明大整数的代价。
Python 版本另外和卡特兰数公式对 n 从 1 到 19 做了对拍：
随机对拍 19 组（n 取 1 到 19（超过 19 时答案会超出 32 位整数）），solve 与 brute 的结果全部一致。
n 只有 19 种取值，随机取值几乎覆盖全部，固定用例已经包含 n = 19 这个最大值。另外四种语言只在上面 12 组固定用例上验证过。
下面的演示用 n = 5，答案 42。每一步展示 dp[k] 是怎么由更小的 dp 相乘再相加得到的：dp[3] = dp[0]×dp[2] + dp[1]×dp[1] + dp[2]×dp[0] = 2 + 1 + 2 = 5（根依次取第 1、2、3 小的数）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。