95. 不同的二叉搜索树 II

**不同二叉搜索树II**

在本题中，我们需要找到给定一个整数 `n` 的所有不同的二叉搜索树（BST）的数量。二叉搜索树是一棵空树或具有以下性质的二叉树：

* 左子树中所有元素都小于根节点。
* 右子树中所有元素都大于根节点。

**解决方案**

我们可以使用递归来解决这个问题。对于每个整数 `i`，我们需要找到 `i-1` 个左子树和 `n-i` 个右子树的数量，然后将它们相乘并加上1（因为有一个空树）。

class Solution:
 def numTrees(self, n: int) -> int:
 # 初始化dp数组，dp[i]表示i个节点的不同BST的数量 dp = [0]*(n+1)
 # base case：当n=0时，有一棵空树 dp[0] =1 # 遍历每个整数i for i in range(1, n+1):
 # 初始化左子树和右子树的数量 left = right =0 # 遍历每个可能的根节点j for j in range(i):
 # 左子树中有j-1棵BST，右子树中有i-j棵BST left += dp[j]
 right += dp[i-j]
 # 将左子树和右子树的数量相乘并加上1（因为有一个空树）
 dp[i] = left * right # 返回n个节点的不同BST的数量 return dp[n]