题目描述
给定一个整数 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]