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,…,m]和[i+1,…,i+m]能够构造BST的数目是相同的，不妨将原问题转化为求n个连续的数能够构成BST的数目

考虑分别以1,2,…i…,n为root，左子树由1~i-1这i-1个数构成，右子树有i+1~n这n-i-2个数构成，左右子树数目相乘即可，然后再累加

 

代码：

1 int numUniTrees(int n, vector
      
        &res){ 2     if(res[n] != -1)  3         return res[n]; 4      5     if(n == 0||n == 1){ 6         res[n] = 1; 7         return res[n]; 8     } 9     10     int num = 0;11     for(int i = 0; i < n; i++){12         //num += numTrees(i)*numTrees(n-i-1);//剥离出来一个函数之后，注意更改函数名13         num += numUniTrees(i, res) * numUniTrees(n-i-1, res);14     }15     res[n] = num;16     return res[n];17 }18 int numTrees(int n) {19     if(n < 0) 20         return 0;21     vector
       
        res(n+1, -1);22     return numUniTrees(n, res);23 }