不同的二叉搜索树

今天药忘吃喽~ 2022-02-09 08:19 147阅读 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][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][https_blog.csdn.net_weixin_38481963_article_details_87989227]

[https_blog.csdn.net_wookaikaiko_article_details_81105031]: https://blog.csdn.net/wookaikaiko/article/details/81105031
[https_blog.csdn.net_weixin_38481963_article_details_87989227]: https://blog.csdn.net/weixin_38481963/article/details/87989227

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

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

相关阅读

相关 95. 不同的二叉搜索树 II

95. 不同的二叉搜索树 II 给你一个整数 n, 请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。

心已赠人/ 2024年04月01日 18:55/ 0 赞/ 14 阅读

相关 LeetCode-96. 不同的二叉搜索树

题目来源 [96. 不同的二叉搜索树][96.] 递归 1.我们要知道二叉搜索树的性质，对于一个二叉搜索树，其【左边的节点值 < 中间的节点值 < 右边的节点值】

朱雀/ 2024年03月26日 18:36/ 0 赞/ 16 阅读

相关 LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ

> 微信搜一搜：`bigsai` > [算法文章题解全部收录在github仓库bigsai-algorithm][github_bigsai-algorithm] >

谁借莪１个温暖的怀抱￠/ 2023年01月01日 10:54/ 0 赞/ 75 阅读

相关 95. 不同的二叉搜索树 II

题目来源 [95. 不同的二叉搜索树 II][95. _ II] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGV

我会带着你远行/ 2022年12月24日 00:38/ 0 赞/ 72 阅读

相关 96. 不同的二叉搜索树

题目来源 [96. 不同的二叉搜索树][96.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

女爷i/ 2022年12月23日 06:18/ 0 赞/ 101 阅读

相关 leetcode 96 不同的二叉搜索树

前言题目：[96. 不同的二叉搜索树][96.] 参考题解：[不同的二叉搜索树-代码随想录][-] -------------------- 提交代码这道

川长思鸟来/ 2022年09月16日 06:22/ 0 赞/ 101 阅读

相关算法：不同的二叉搜索树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2022年04月10日 13:41/ 0 赞/ 146 阅读

相关 leetcode 96. 不同的二叉搜索树

递归 n个结点轮流做根节点，然后左右进行递归，两个结果做乘法发现20个就超int，打表只需要到19 include <iostream> includ

旧城等待，/ 2022年02月16日 05:01/ 0 赞/ 115 阅读

相关不同的二叉搜索树

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

今天药忘吃喽~/ 2022年02月09日 08:19/ 0 赞/ 148 阅读

相关分治---不同的二叉搜索树

不同的二叉搜索树 [95. Unique Binary Search Trees II (Medium)][95. Unique Binary Search Trees

灰太狼/ 2021年11月29日 07:54/ 0 赞/ 186 阅读