Code & Fun

第29天。

今天的题目是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.

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3

对于这种问题一般都可以用递归去做的,我们尝试的找一下递归式。

n=1 -> 1
n=2 -> 2
n=3 -> 5

我们考虑n=3时的情况,这时这棵树种包含三个值1,2,3,这说明树根的可能是1,2,3中的一个值:

  • root=1时,2,3只能放在右子树。现在只考虑2,3两个值,由于BST的性质,右子树也必须是BST,则此时问题转换成求numsTrees(2).
  • root=2时,左边必定是1,右边必定是3.
  • root=3时,左边必定是1,2,同样转换成numsTrees(2).

我们再考虑一下n=5时的情况:

  • root=3,左子树必定是是包含1,2的BST,右子树必定是包含4,5的BST,此时种类为numsTree(5-3)*numsTrees(3-1)

所以我们可以找到递推式:

  • n < 2 -> numsTrees(n) = 1
  • n >= 2 -> numsTrees(n) = numsTrees(1)*numsTrees(n-1) + numsTrees(2)*numTree(n-2) + ... + numsTree(n-1)*numsTrees(1);

所以我们写出一个递归的解决方案:

1
2
3
4
5
6
7
8
9
10
11
int numTrees(int n) {
if (n <= 1) return 1;

int ret = 0;
for(int i = 1;i <= n;i++) {
int left = i-1;
int right = n-i;
ret += numTrees(left)*numTrees(right);
}
return ret;
}

但是这里会超时,很明显这里可以用动态规划来优化:

1
2
3
4
5
6
7
8
9
10
int numTrees(int n) {
vector<int> ret(n+1);
ret[0] = 1;
ret[1] = 1;
for(int i = 2;i <= n;i++) {
for(int j = 1;j <= i;j++)
ret[i] += ret[j-1]*ret[i-j];
}
return ret[n];
}

dicuss中基本都是和上面类似的解法,除了一个:

1
2
3
4
5
6
7
8
9
int numTrees(int n) {
//cantalan树
//C(2n,n)/(n+1)
long long ans =1;
for(int i=n+1;i<=2*n;i++){
ans = ans*i/(i-n);
}
return ans/(n+1);
}

emmm,说实话,我没看懂,但是这个方法的确是最快的,只需要O(n)的时间,O(1)的空间。


本文首发于Code & Fun