Givenn, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Givenn= 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
给出n，问由 1...n为节点组成的不同的二叉查找树有多少种？
思路：
可以用分治的方法解决，二叉查找树大家都知道，左子树都小于root,右子树都大于root。求n个二叉查找树的不同排列总类，以i为分割,我可以求前i个节点的总类和后n-i-1个节点的总类，这样以第i个节点为root的二叉树一共有kind[0~i]*kind[i~n]种,然后把从0到n的总数相加，最后就是我要的结果。不难想到这个是一个递归的过程，求前i个节点总类的时候，又把i分为两部分，同样后n-i-1个节点也是一样的。如果只有一个节点，当然只有一种结果，所以递归出口是返回1。
根据以上分析，不难写出代码：
long getBinaryTreeKinds(long nodeCount)
{
if (nodeCount <= 1)
{
return 1;
}
long result = 0;
for (int i = 0; i < nodeCount; i++) {
result += getBinaryTreeKinds(i)*getBinaryTreeKinds(nodeCount-i-1);
}
return result;
}
但是这个递归我们可以优化一下，因为它存在太多的重复计算，我们可以用一个数组保存每次计数的结果，这样会大大提高效率。
优化后的代码:
long binaryTreeKindCount(long n)
{
long *count = malloc((n + 1)*sizeof(long)); // 保存每次计算的结果，防止重复计算
memset(count, 0, (n + 1)*sizeof(long)); // 清零防止脏数据
long r = getBinaryTreeKindsFaster(n, count);
free(count);
return r;
}
long getBinaryTreeKindsFaster(long nodeCount,long count[])
{
if (nodeCount <= 1)
{
return 1;
}
long result = 0;
for (int i = 0; i < nodeCount; i++) {
if (count[i] == 0) {
count[i] = getBinaryTreeKindsFaster(i,count);
}
if (count[nodeCount-i-1] == 0) {
count[nodeCount-i-1] = getBinaryTreeKindsFaster(nodeCount-i-1,count);
}
result += count[i]*count[nodeCount-i-1];
}
return result;
}
网友评论