目标：

给出节点数，输出可以生成多少颗二叉搜索树的数量。

 

主要思路：

主要考察对搜索二叉树的理解，考虑分状况，当选择最小的节点或最大节点当树节点，则剩下的情况就等于F(n - 1)。当选择中间节点，则为F(1) * F(n - 2) + F(2) * F(n - 3) + ... + F(n-3) * F(2) + F(1) * F(n - 2)这么多种情况。

所以总的F(n) = F(n - 1) + F(1) * F(n - 2) + F(2) * F(n - 3) + ... + F(n-3) * F(2) + F(1) * F(n - 2) + F(n - 1)

参考：

 

代码：

1 class Solution { 2 public: 3     int numTrees(int n) { 4         if (n == 1) return 1; 5         int sum = 0; 6         sum += 2 * numTrees(n - 1); 7         for (int i = 1; i < n - 1; i++) { 8             sum += numTrees(i) * numTrees(n - 1 - i); 9         }10         return sum;11     }12 };