leetcode[94] Unique Binary Search Trees
給定n，那麼從1,2,3...n總共可以構成多少種二叉查找數呢。例如給定3
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
思路：
我們考慮頭結點i，那麼所有比i小的都在i的左邊，比i大的都在i的右邊。也就是以i為開頭的是i的左邊的可能*i右邊的可能，然後遍歷i從1到n，所有可能相加就是我們的結果。
由公式 h[n] = h[0]*h[n-1] + h[1]*h[n-1] + ... + h[n-1]*h[0]; 可得如下：
復制代碼
class Solution {
public:
int numTrees(int n) {
if (n == 1) return 1;
vector<int> ans(n+1);
ans[0] = 1;
ans[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 0; j < i; j++)
{
ans[i] += ans[j]*ans[i-j-1];
}
return ans[n];
}
};
復制代碼
其實這是一個卡特蘭數，直接用公式C2n選n除以n+1則如下：
復制代碼
class Solution {
public:
int numTrees(int n) {
if (n == 1) return 1;
long long denominator = 1, numerator = 1;
int cnt = 2 * n;
while(cnt > n) denominator *= cnt--;
while(cnt > 0) numerator *= cnt--;
return denominator/numerator/(n+1);
}
};
復制代碼
還可以用遞歸：
復制代碼
class Solution {
public:
int numTrees(int n)
{
return numTrees(1,n);
}
int numTrees(int start, int end)
{
if (start >= end)
return 1;
int totalNum = 0;
for (int i=start; i<=end; ++i)
totalNum += numTrees(start,i-1)*numTrees(i+1,end);
return totalNum;
}
};
