【问题】
卡特兰（Catalan）数来源于卡特兰解决凸n+2边形的剖分时得到的数列Cn，在数学竞赛、信息学竞赛、组合数学、计算机编程等方面都会有其不同侧面的介绍．卡特兰问题的解决过程应用了大量的映射方法，堪称计数的映射方法的典范．
假设h(0) = 1, h(1) = 1, 则卡特兰数满足以下递推式：
h(n) = h(n-1) * (4 * n-2)/(n+1)----十分重要的递推式
那么，给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
【思路】
由于题目是不同的二叉搜索树，那么就与每个节点的值无关了，只考虑构成二叉树的结构问题！
思路一：使用动态规划算法，假设有i个节点构成二叉树，以根节点分割，左子树有j个节点，则：
dp[i] = dp[j] * dp[i-j-1]
其中dp[i]表示节点总数为i时可以有多少种方案，就等于左子树的方案数*右子树的方案数
思路一：动态规划 class Solution { public: int numTrees(int n) { vector<long> dp(n+1); dp[0] = 1, dp[1] = 1; for(int i = 2; i <= n; i++){ for(int j = 0; j < i; j++){ dp[i] += dp[j] * dp[i-j-1]; } } return dp[n]; } };
思路二：使用卡特兰数递推式，由于二叉树的构成问题属于卡特兰数的一种应用！我们可以直接使用递推式得到最终的结果！
思路二：卡特兰数 class Solution { public: int numTrees(int n) { long h = 1; for(long i = 1; i <= n; ++i){ h = h * (4*i-2) / (i+1); } return h; } };
原文：https://www.cnblogs.com/zhudingtop/p/11678964.html