Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
Example
Given n = 3, there are a total of 5 unique BST’s.
1
2
3
4
5
| 1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
|
Solution
对于任意以i为根节点的二叉树，它的左子树的值一定小于i，也就是[0, i - 1]区间，而右子树的值一定大于i，也就是[i + 1, n]。假设左子树有m种排列方式，而右子树有n种，则对于i为根节点的二叉树总的排列方式就是m x n。
我们使用dp[i]表示i个节点下面二叉树的排列个数，那么dp方程为:
dp[i] = sum(dp[k] * dp[i - k -1])
Java
(Unique-Binary-Search-Trees.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
if (n<2)
return 1;
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i=3;i<=n;i++){
int sum = 0;
for(int j=0;j<i;j++){
sum += dp[j]*dp[i-j-1];
}
dp[i] = sum;
}
return dp[n];
}
}
|
(Unique-Binary-Search-Trees.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
#dp: how many unique trees
#dp[1] = 1
#dp[2] = 2
#dp[3] = 5 = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
#dp[n] = sum(dp[i] * dp[n-i-1])
dp = [1,1,2]
if n < 3:
return dp[n]
for i in range(3,n+1):
sum = 0
for j in range(0,i):
sum += dp[j]*dp[i-j-1]
dp.append(sum)
return dp[n]
|