?
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 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;
? ? }
};