二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
G ( n ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + f ( 4 ) + . . . + f ( n ) G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n) G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
f ( i ) = G ( i 1 ) G ( n i ) f(i) = G(i-1)*G(n-i) f(i)=G(i1)G(ni)
综合两个公式可以得到 卡特兰数 公式
G ( n ) = G ( 0 ) G ( n 1 ) + G ( 1 ) G ( n 2 ) + . . . + G ( n 1 ) G ( 0 ) G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0) G(n)=G(0)G(n1)+G(1)G(n2)+...+G(n1)G(0)
G(n)函数的值被称为 卡特兰数，卡特兰数更便于计算的定义如下:
C 0 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n C0=1,Cn+1={2(2n+1)over n+2}Cn C0=1,Cn+1=n+22(2n+1)Cn
卡特兰数：
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452
所求即为：G（n）
class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i < n + 1; i++) for(int j = 1; j < i + 1; j++) dp[i] += dp[j-1] * dp[i-j]; return dp[n]; }}
官方题解：
class Solution { public int numTrees(int n) { // Note: we should use long here instead of int, otherwise overflow long C = 1; for (int i = 0; i < n; ++i) { C = C * 2 * (2 * i + 1) / (i + 2); } return (int) C; }} 62021754
