本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/43198929
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路：
（1）题意为给定n个节点，求能组成多少个二叉树。
（2）该题和给定n个数字，求其所有进栈出栈顺序总个数是相同的，详情参看数据结构。
（3）本题是运用递归进行实现。
递推关系为： f(n)=C(2n,n)/(n+1) (n=1,2,3,...)。
递归式为： f(n)=f(n-1)*(4*n-2)/(n+1)。
通过该公式进行递归即可得到答案。但是通过递归实现的算法效率显然要低一些。
递推过程：
当n=1时，只有1个根节点，则能组成1种，令n个节点可组成的二叉树数量表示为f(n)， 则f(1)=1;
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树， 即：f(2)=f(0)*f(1)+f(1)*f(0)=2，则能组成2种。
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树， 即：f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5，则能组成5种。
当n>=2时，有f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0)
（4）希望本文对你有所帮助。
算法代码实现如下：
/**
* @author liqq
*/
public int numTrees(int n) {
int i;
int result = 0;
if(n==0) return 1;
if(n==1) return 1;
for (i = n-1; i>=0 ; i--) {
result = result + numTrees(i)*numTrees(n-i-1);
}
return result;
}