leetcode解题: Unique Binary Search Trees (96)

发表于 | 分类于

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.

解法：DP with O(N^2) time and O(N) space

通常count的问题也可以考虑用dp的方法求解。由于是binary search trees,那么首先要搞清楚的是binary search tree的结构：
1 root左边的所有节点一定比root小
2 root右边的所有节点一定比root大
如果我们有N个数字可以选择，那么如果选择了一个i为root,则1 ~ （i -1)都必须在左子数，(i + 1) ~ N 都必须在右子数
具体每一个子数有多少unique的排列则完全取决于node的个数。
那么我们可以用memorization的思想，从1个node开始，存下每个node可能的排列个数，然后对每一个可能作为root的计算相应的子数的个数。对应的算法为O(N^2)的Time complexity
举例，如果N = 3
那么可以成为root的有1，2，3三个数
当1作为root的时候，由于他是最小值，则剩下的2个数只能排放右边，故排列数为num(2)
当2作为root的时候，比他小的数有一个，比他大的数有1个，分列左右两边，故排列数为num(1) * num(1)
当3作为root的时候，同理1，他是最大值，排列数为num(1) * num(1)
所以总的排列数是每个情况的相加,只要知道了num(1)和num(2)就可以求出num(3)

同时，这个问题也是Catalan Number的一个应用，具体可以看Wiki

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int numTrees(int n) {
	
	if (n <= 0) {
		return 1; // If no nodes, then just an empty tree, so 1
	}
	
	int[] dp = new int[n + 1];
	dp[0] = 1;	// empty tree
	dp[1] = 1;	// single node tree
	
	for (int i = 2; i <= n; i++) {
		int sum = 0;
		for (int j = 1; j <= i; j++) {
			int left = j - 1;	// number of left node
			int right = i -  j;	// number of right node
			sum += dp[left] * dp[right];	// multiply 
		}
		dp[i] = sum;
	}
	
	return dp[n];
}