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

 

 

Solution 1:  递归

1 class Solution { 2 public: 3     int numTrees(int n) { 4         if(n == 0) 5             return 1; 6         else if(n == 1) 7             return 1; 8         else 9         {10             int count = 0;11             for(int i = 0; i <= (n-1)/2; i ++)12             {13                 if(i < n-1-i)14                     count += 2*numTrees(i)*numTrees(n-1-i);15                 else16                     count += numTrees(i)*numTrees(n-1-i);17             }18             return count;19         }20     }21 };

 

Solution 2: dynamic programming . Base case: n==0, n==1时，f(n)==1, f(n)=∑f(i)*f(n-i-1)。即以第i个为根节点，左右子树数目相乘 

class Solution {public:    int numTrees(int n) {        if(n<2)return 1;                vector
     
       v(n+1, 0);        v[0]=1;        v[1]=1;        for(int i=2;i