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為節(jié)點(diǎn)組成的不同的二叉查找樹有多少種？
思路：
可以用分治的方法解決，二叉查找樹大家都知道，左子樹都小于root,右子樹都大于root。求n個(gè)二叉查找樹的不同排列總類，以i為分割,我可以求前i個(gè)節(jié)點(diǎn)的總類和后n-i-1個(gè)節(jié)點(diǎn)的總類，這樣以第i個(gè)節(jié)點(diǎn)為root的二叉樹一共有kind[0~i]*kind[i~n]種,然后把從0到n的總數(shù)相加，最后就是我要的結(jié)果。不難想到這個(gè)是一個(gè)遞歸的過程，求前i個(gè)節(jié)點(diǎn)總類的時(shí)候，又把i分為兩部分，同樣后n-i-1個(gè)節(jié)點(diǎn)也是一樣的。如果只有一個(gè)節(jié)點(diǎn)，當(dāng)然只有一種結(jié)果，所以遞歸出口是返回1。
根據(jù)以上分析，不難寫出代碼：
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;
}
但是這個(gè)遞歸我們可以優(yōu)化一下，因?yàn)樗嬖谔嗟闹貜?fù)計(jì)算，我們可以用一個(gè)數(shù)組保存每次計(jì)數(shù)的結(jié)果，這樣會(huì)大大提高效率。
優(yōu)化后的代碼:
long binaryTreeKindCount(long n)
{
? ? long *count = malloc((n + 1)*sizeof(long)); // 保存每次計(jì)算的結(jié)果，防止重復(fù)計(jì)算
? ? memset(count, 0, (n + 1)*sizeof(long)); // 清零防止臟數(shù)據(jù)
? ? 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;
}
