Givenn, how many structurally uniqueBST’s(binary search trees) that store values 1…n?
For example,Givenn= 3, there are a total of 5 unique BST’s.
13321\/// \\3211 32//\\ 2123给定一个数n，求1到n这些数可以构成多少棵二叉树。
给定一个序列1…..n，为了构造所有二叉树，我们可以使用1……n中的每一个数i作为根节点，自然1……(i-1)必然位于树的左子树中，(i+1)…..n位于树的右子树中。然后可以递归来构建左右子树，由于根节点是唯一的，所以可以保证构建的二叉树都是唯一的。
使用两个状态来记录：
G(n)：长度为n的序列的所有唯一的二叉树。
F(i,n)，1<=i<=n：以i作为根节点的二叉树的数量。
G(n)就是我们要求解的答案，G(n)可以由F(i,n)计算而来。
G(n)=F(1,n)+F(2,n)+…+F(n,n) (1)
G(0)=1,G(1)=1
对于给定的一个序列1…..n，我们取i作为它的根节点，那么以i作为根节点的二叉树的数量F(i)可以由下面的公式计算而来：
F(i,n)=G(i-1)*G(n-i) 1<=i<=n (2)
综合公式（1）和公式（2），，可以看出：
G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
这就是上面这个问题的答案。
参考自：https://leetcode.com/discuss/24282/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i
可以看出这个问题和斐波拉也数列一样既可以用递归求解，也不可以不用递归求解，但是在leetcode中使用递归求解会显示超时。但是执行结果还是正确的。
解法一：递归解法
runtime:0ms
class Solution {public:int numTrees(int n) {if(n==0||n==1)return 1;int result=0;for(int i=0;i<n;i++)result+=numTrees(i)*numTrees(n-i-1);return result;}};
解法二：非递归解法
class Solution {public:int numTrees(int n) {int *G=new int[n+1]();G[0]=1;G[1]=1;for(int i=2;i<=n;i++){for(int j=0;j<i;j++)G[i]+=G[j]*G[i-j-1];}return G[n];}};
解法三：数学公式
数学上有一个卡塔兰数(Catalan)：
令h(0)=1,h(1)=1，卡塔兰数数满足递归式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + … + h(n-1)h(0) (其中n>=2),这是n阶递归关系;
该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!)(n=1,2,3,…)
所以可以直接使用这个递归公式进行求解：
class Solution {public:int numTrees(int n) {long long ans=1;for(int i=n+1;i<=2*n;i++){ans=ans*i/(i-n);}return ans/(n+1);}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
生气是拿别人做错的事来惩罚自己
