不同的二叉搜索树
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3
思路+代码+注释:
卡塔兰数列的递推式为:
public int numTrees(int n) { /* 思路:n=0时为空树,因为空树也算是二叉查找树的一种所以个数为1 n>=1时,二叉查找树的个数等于根节点左子树个数*根节点右子树个数 dp[n]记录0~n对应的二叉查找树的个数 dp[0]=1 dp[1]=dp[0]*dp[0] n==2时,根节点可以是1和2 dp[2]=dp[0]*dp[1]+dp[1]*dp[0] n==3时,根节点可以是1、2、3 dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0] 由此可以推出卡塔兰数列的递推式 */ //加上n=0是n+1种情况 int[] dp=new int[n+1]; dp[0]=1; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { dp[i+1]+=dp[j]*dp[i-j]; } } return dp[n]; }
c/c++开发分享96. 不同的二叉搜索树地址:https://blog.csdn.net/qq_36059306/article/details/85986785
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598944.html