LeetCode-96. 不同的二叉搜索树
题目来源
96. 不同的二叉搜索树
题目详情
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入： n = 3
输出： 5
示例 2：
输入： n = 1
输出： 1
提示：
1 <= n <= 19
题解分析
解法一：动态规划
题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：
-
G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。
-
F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 \((1 \leq i \leq n)\)。
可见，G(n) 是我们求解需要的函数。
稍后我们将看到，G(n) 可以从 F(i, n) 得到，而 F(i, n) 又会递归地依赖于 G(n)。
首先，根据上一节中的思路，不同的二叉搜索树的总数 G(n)，是对遍历所有 i \((1 \le i \le n)\) 的 F(i, n) 之和。换言之：
\[G(n) = \sum_{i=1}^{n} F(i, n)\qquad \qquad (1) \]对于边界情况，当序列长度为 1（只有根）或为 0（空树）时，只有一种情况，即：
\[G(0) = 1, \qquad G(1) = 1 \]给定序列 \(1 \cdots n\)，我们选择数字 i 作为根，则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树，如下图所示：
举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 [1, 2, 3, 4, 5, 6, 7]，我们需要从左子序列 [1, 2] 构建左子树，从右子序列 [4, 5, 6, 7] 构建右子树，然后将它们组合（即笛卡尔积）。
对于这个例子，不同二叉搜索树的个数为 F(3, 7)。我们将 [1,2] 构建不同左子树的数量表示为 G(2), 从 [4, 5, 6, 7] 构建不同右子树的数量表示为 G(4)，注意到 G(n) 和序列的内容无关，只和序列的长度有关。于是，\(F(3,7) = G(2) \cdot G(4)\)。 因此，我们可以得到以下公式：
\[F(i, n) = G(i-1) \cdot G(n-i) \qquad \qquad (2) \]将公式 (1)，(2) 结合，可以得到 G(n) 的递归表达式：
\[G(n) = \sum_{i=1}^{n}G(i-1) \cdot G(n-i) \qquad \qquad (3) \]至此，我们从小到大计算 G 函数即可，因为 G(n) 的值依赖于 \(G(0) \cdots G(n-1)\)。
class Solution {
public int numTrees(int n) {
// G(n)表示节点个数为n的二叉树种类，F(i, n)表示以i为根节点的节点数为n的二叉树种类
// G(n) = F(1, n) + F(2, n) + ... + F(n, n)
// F(i, n) = G(i - 1) * G(n - i) // 给定序列 1?n，我们选择数字 i 作为根，则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积
// G(n) = [G(1 - 1) * G(n - 1)] + [G(2 - 1) * G(n - 2)] + ... + [G(n - 1) * G(n - n)]
int[] g = new int [n + 1];
g[0] = 1;
g[1] = 1;
for(int i=2; i<=n; i++){
for(int j = 1; j<=i; j++){
g[i] += g[j - 1] * g[i - j];
}
}
return g[n];
}
}
结果展示
