Leetcode-96 Unique Binary Search Trees

发表于 | 分类于 | 次

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example 1

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
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

解题思路

动态规划。定义 dp[l] 表示 n=l 时 BST 的数量。以每个数 $i\in [1,l]$ 为根节点，左子树有 i-1 个节点，右子树有 l-i 个节点，所以 BST 的数量 $dp[l]=\sum_{i\in [1,l]} dp[i-1]*dp[l-i]$。

BST 的数量属于卡特兰数，满足公式：$C_{2n}^{n}/(n+1),\ n=(0,1,2,…)$。

复杂度分析

  • 时间复杂度：$O(n^2)$，两个循环。
  • 空间复杂度：$O(n)$，动态规划数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
	int numTrees(int n) {
		//dp[l] 表示长度为 l 的序列对应的树的个数
		vector<int> dp(n + 1, 0);
		for (int l = 0; l <= n; ++l) {
			if (l < 2) {
				dp[l] = 1;
				continue;
			}
			for (int i = 1; i <= l; ++i) {
				dp[l] += dp[l - i] * dp[i - 1];
			}
		}
		return dp[n];
	}
};