不同的二叉搜索树

给定一个整数 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