难度: Medium
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
Submission
运行时间: 40 ms
内存: 14.8 MB
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
Explain
这个题解使用动态规划的思路来解决问题。定义 dp[i] 表示具有 i 个节点的不同二叉搜索树的个数。对于 i 个节点，可以枚举根节点的位置 j（从1到i），那么左子树就有 j-1 个节点，右子树有 i-j 个节点。由于左右子树也都是二叉搜索树，因此可以递归地计算它们的个数，然后相乘得到以 j 为根节点的二叉搜索树的个数。最后将所有 j 的情况累加起来，就得到了 i 个节点的不同二叉搜索树的总数。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1) # 定义 dp 数组，dp[i] 表示具有 i 个节点的不同二叉搜索树的个数
dp[0] = 1 # 空树也算一种情况
dp[1] = 1 # 只有一个节点的树只有一种情况
for i in range(2, n+1): # 遍历节点数 i 从 2 到 n
for j in range(1, i+1): # 枚举根节点的位置 j 从 1 到 i
dp[i] += dp[j-1] * dp[i-j] # 左子树有 j-1 个节点，右子树有 i-j 个节点，将它们的个数相乘并累加到 dp[i]
return dp[n] # 返回具有 n 个节点的不同二叉搜索树的个数
Explore
在定义 dp 数组时，dp[0] 被初始化为 1 是因为在构建二叉搜索树时，如果一个树没有任何节点，我们称之为空树。在递归构建树的过程中，空树作为递归的基本情况，它代表了一种可能的结构（即没有结构），因此计数为 1。在数学上，空集也被认为是一个有效的集合，其元素个数为 0。在二叉搜索树的上下文中，空树是节点数为 0 的树的唯一表示形式，它在计算具有更多节点的树的数目时作为基本案例存在。
递推公式 dp[i] += dp[j-1] * dp[i-j] 是基于二叉搜索树的性质构建的。在这个公式中，当我们选择第 j 个元素作为根节点时，所有小于 j 的元素必须构成左子树，且这些元素的排列方式也应该形成二叉搜索树，其数量由 dp[j-1] 给出；而所有大于 j 的元素形成右子树，其排列方式的数量由 dp[i-j] 给出。由于 j 的选择保证了左子树中的所有值都小于根，右子树中的所有值都大于根，这自然保持了二叉搜索树的性质。
在递归计算树的数量时，确实存在重复计算的情况。例如，在计算 dp[4] 时，我们可能多次计算 dp[2] 或其他较小的 dp 值。动态规划通过建立一个表（dp 数组）来存储已解决子问题的结果来解决这个问题，这种方法称为 'memoization' 或 '表格化'。这样，每个子问题只计算一次，并保存其结果，后续的计算可以直接使用这些结果，避免了重复计算，从而显著提高了效率。
当 n 增大时，dp 数组中的值呈现出超线性的增长趋势，这是因为每增加一个节点，新的树的数量是通过以每个节点作为根节点的方式，组合所有可能的左右子树来形成的。因此，dp[n] 的值是所有可能的左子树数量与右子树数量的乘积的累积。这种组合的增长速度远超线性，实际上与卡特兰数密切相关，其增长速度类似于 (4^n)/(n^(3/2))，这表明了随着 n 的增加，二叉搜索树的结构变得极其多样化。