Leetcode 96. 不同的二叉搜索树
题目描述
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例 1:
解法
不妨以
f(i)
表示
i
个整数能够组成的二叉搜索树的种类数。则对于
n
个整数组成搜索树的种类数，需要分别计算出左子树个数为
0
时二叉树的种类数，左子树个数为
1
时二叉树的种类数......左子树个数为
n-1
时二叉树的种类数，然后相加即可。
若整数个数为
n
，当左子树个数为
x
时，则右子树个数为
n-1-x
，此时二叉树的种类数为
f(x)*f(n-1-x)
。
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]本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.07.13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
