题目描述
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例 1:
解法
不妨以 表示
个整数能够组成的二叉搜索树的种类数。则对于
个整数组成搜索树的种类数，需要分别计算出左子树个数为
时二叉树的种类数，左子树个数为
时二叉树的种类数......左子树个数为
时二叉树的种类数，然后相加即可。
若整数个数为
，当左子树个数为
时，则右子树个数为
，此时二叉树的种类数为
。
class Solution:
def numTrees(self, n: int) -> int:
dp=[1]*(n+1)
for i in range(2,n+1):
tmp=0
for j in range(0,i):
tmp=tmp+dp[j]*dp[i-1-j]
dp[i]=tmp
return dp[n]
