[Leetcode 96] Unique Binary Search Trees

作者 Shilei Tian 日期 2017-02-11
[Leetcode 96] 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

解题思路

由于 BST 的中序遍历是一个递增序列,每一种不同的前序遍历就对应一个序列的排列,所以我最初的想法是这道题目应该和排列组合有关,枚举序列所有可能的排列组合方式,然后再排除那些不是 BST 的。但是仔细想一下,时间复杂度太高。这一道题目只是让求出数量来,并没有要求返回所有的 BST,因此这个方法不可取。

那么就得想一下别的思路了,是不是这道题目可以用动态规划来解?考虑序列 [1, 2,..., n],在所有可能的 BST 中,我们可以将它们分成 n 类,每一类的 BST 都是以 i 作为根节点。那么我们记 F(n) 为存储 [1,…,n] 值不同 BST 的数量,F(i,n) 为以 i 为根节点,存储存储 1…n 值不同 BST 的数量。由此,我们很容易得出:F(n) = F(1, n) + F(2, n) +…+ F(n,n),并且 F(0) = 1F(1) = 1

接下来我们来考虑 F(i, n) 如何求,我们现在已经知道,i 是根节点,那么 i 的左子树肯定是由序列 [1,…,n - 1] 组成,那么很自然地我们就可以用 F(n - 1) 来表示左子树不同 BST 的数量。右子树由 [i + 1,…, n] 组成,那么它一共有多少种情况呢?这个时候你可能有些不知所措,但其实,我说它一共有 F(n - i) 中情况。为什么呢?F(n - i) 不是应该是存储 [1,…, n-i] 序列的情况吗?是的!尝试如果将序列 [i + 1,…, n] 每个元素都减 i,我们就可以得到序列 [1,…, n-i] ,并且,元素之间的相对位置并不能发生改变。因此 [1,…, n-i] 有多少种可能,[i + 1,…,n] 就有多少种。因此,我们将左右子树的可能相乘(笛卡尔积),就可以得到以 i 为根节点,存储 [1,…, n] 元素的不同 BST 的数量 F(i, n) = F(i - 1) * F(n - i)。进一步,我们就可以得到,F(n) = F(0) * F(n - 1) + F(1) * F(n - 2) +…+ F(n - 1) * F(0)

有了上面的分析,我们就很容易写出代码来了,如下:

class Solution {
public:
int numTrees(int n) {
vector<int> f(n + 1, 0);
f[0] = 1, f[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= i - 1; ++j) {
f[i] += f[j] * f[i - 1 - j];
}
}
return f[n];
}
};