题目
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.
分析
此题与上题本质相同，LeetCode 95 Unique Binary Search Trees要求得到全部二叉查找树，打印其层序遍历序列。
而此题，只要求元素 [1,n] 能构成的二叉查找树个数。
这是一个动态规划的题目
- 当 n==0 时 ， 自然为 0 ;
- 当 n==1 时 ，可构成 1 颗 ;
- 当 n==2 时 ，可构成 2 颗 ;
- 当 n>2 时，任意 [1,n] 中的值都可做为根节点；
求解方式为：
声明数组 nums[n+1] 记录 1—n为界限时，可构成的二叉查找树数目，最终返回 nums[n] ;
对于界限为 r 时，任一 [1,r] 内一元素均可作为根节点，且 [1,i−1] 为当前左子树，[i+1,r] 为当前右子树；
因为，
[1,i−1] 可构成的子树数目，即等于 lefts=nums[i−1]
[i+1,r] 为 r−i 个连续元素，其构成的子树数目等于 rights=nums[r−i]
故，当 n=r 时，可构成 sum(lefts∗rights)1~r ;
AC代码
class Solution {
public:
int numTrees(int n) {
if (n <= 0)
return 0;
//保存[1,n]每个值对应的二叉查找树个数
vector<int> nums(n+1, 0);
//空子树也算一颗
nums[0] = 1;
for (int r = 1; r <= n; ++r)
{
//当 n == 1 或者 n == 2时，满足要求的树的个数为n
if (r <= 2)
{
nums[r] = r;
continue;
}//if
//对于 [1 , r]之间的每个元素都可作为根节点
for (int i = 1; i <= r; i++)
{
//此时能构成的二叉查找树个数 = [1,i-1]构成的左子树数目 * [i+1 , r]构成的右子树数目
int lefts = nums[i - 1];
//[i+1 , r]为连续的 r-i 个元素，所构成的树数目等于元素[1 , r-i]构成的数目
int rights = nums[r - i];
//
nums[r] += lefts * rights;
}//for
}//for
return nums[n];
}
};