Question

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           1           2          3        3
 \           \         /  \       /        /
  2          3        1    3     1        2
   \        /                     \      /
    3      2                       2    1

求解过程

思路：1...n之间的所有BST数量等于以1...n之间的每个数为根节点的BST之和。

G(n)：表示1...n之间的所有BST数量
F(i,n)：表示以i为根节点的BST数量
G(n)=F(1,n)+F(2,n)+...+F(n,n)
F(i,n)=G(i-1)*G(n-i)  
注：
1...i...n以i为根节点的时候，BST数量等于以1...(i-1)组成的左子树数量乘以(i+1)...n组成的右子树，(i+1)...n组成的BST数量等1...(n-i)能构成的BST数量.
递推公式：
G(n)=G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)      G(0)=1

实现代码

public static int countOfBSTNumber(int n) {    
  if (n < 0) return -1;    
  int[] C = new int[n + 1];    
  C[0] = 1;    
  for (int i = 1; i <= n; i++) {       
    for (int j = 0; j < i; j++) {            
      C[i] += C[j] * C[i - j - 1];        
    }    
   }   
   return C[n];
}

分析：

n is ：1， the number of BST is : 1
n is ：2， the number of BST is : 2
n is ：3， the number of BST is : 5
n is ：4， the number of BST is : 14
n is ：5， the number of BST is : 42
n is ：6， the number of BST is : 132
n is ：7， the number of BST is : 429
n is ：8， the number of BST is : 1430
n is ：9， the number of BST is : 4862
n is ：10， the number of BST is : 16796
n is ：11， the number of BST is : 58786
n is ：12， the number of BST is : 208012
n is ：13， the number of BST is : 742900
n is ：14， the number of BST is : 2674440
n is ：15， the number of BST is : 9694845
n is ：16， the number of BST is : 35357670
n is ：17， the number of BST is : 129644790
n is ：18， the number of BST is : 477638700
n is ：19， the number of BST is : 1767263190
n is ：20， the number of BST is : -2025814172

可以看到当n=20的时候，所构成的BST的数量以前超过了int能够表示的数范围了。