不同的二叉搜索树

今天药忘吃喽~ 2022-02-09 08:19 334阅读 0赞

题目
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3

求解思路：
卡特兰数详解
https://blog.csdn.net/wookaikaiko/article/details/81105031
思路：
就跟斐波那契数列一样，我们把
n = 0 时赋为1，因为空树也算一种二叉搜索树，
n = 1时的情况可以看做是其左子树个数乘以右子树的个数，左右字数都是空树，所以1乘1还是1。
n = 2时，由于1和2都可以为跟，分别算出来，再把它们加起来即可。n = 2的情况可由下面式子算出：
dp[2] = dp[0] * dp[1]　　　(1为根的情况)
　　　　+ dp[1] * dp[0]　　 (2为根的情况)

同理可写出 n = 3 的计算方法：
dp[3] = dp[0] * dp[2]　　　(1为根的情况)
　　　　+ dp[1] * dp[1]　　 (2为根的情况)
　　　 + dp[2] * dp[0]　　 (3为根的情况)
由此可以得出卡塔兰数列的递推式为：
C0 = 1 and C n+1 = 求和 CiCn-i （n>=0）
即
dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2]+…+dp[n-2]*dp[1]+dp[n-1]*dp[0];

java实现代码
https://blog.csdn.net/weixin_38481963/article/details/87989227

发表评论

表情：
评论列表 （有 0 条评论，334人围观）

还没有评论，来说两句吧...

相关阅读