版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
-
Unique Binary Search Trees
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.
题目大意：给定一个数字n，有多少个结点值为1~n的唯一二叉搜索树？
例如：给定n=3，共有5个二叉搜索树。思路（递归）：二叉搜索树的性质，左边的数都比根小，右边的数都比根大。二叉树的节点是从1到n，所以能确定如果根为k，则根左边的数是1到k-1，根右边的数是k+1到n。对于一个根来说，唯一二叉树的数量是其左子树的数量乘以右子树的数量。也就是说，假如有n个结点，则唯一二叉搜索树的个数为f(n) = f(0)·f(n-1) + f(1)·f(n-2) + ... + f(n-1)·f(0)，意思是，当根节点为1的时候，左子树有0个，右子树有n-1个，相乘即得此时的唯一二叉树个数；当根节点为2的时候，左子树有1个，右子树有n-2个，相乘即得此时的唯一二叉树个数；以此类推，当最后根节点为n时，左子树有n-1个，右子树有0个，相乘即得此时的唯一二叉树个数。
代码（递归）
int numTrees(int n)
{
if(n == 0)return 1;
if(n == 1)return 1;
int res = 0;
for(int i = 0; i < n; i++)
{
// 假设当前的根节点是i+1（从0开始，root结点值应该加一）
// 则左子树有0~i个，右子树是（i+2）~n个
res += numTrees(i) * numTrees(n-i-1);
}
return res;
}
- 思路（非递归）：还有一种是用动态规划的思想去做，理解了递归的思想，非递归的思想也就很好理解了，其实就是把递归改写成了循环，具体是把递归得到的数据存到一个一位数组中；时间复杂度O(N!)，空间复杂度O(N)。
int numTrees(int n) {
int* res = new int[n+1];
res[0] = 1;
res[1] = 1;
for(int i = 2; i <= n; i++)
{
res[i] = 0;
for(int j = 0; j < i; j++)
{
res[i] += res[j] * res[i-j-1];
}//for
}//for
return res[n];
}
- 以上。
版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~
