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
2
3
4
5
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

分析


最重要的是找到其中的规律。定义f(n)表示以1..n形成的二叉搜索树的数目,如果n=0,是一种BST,即空树,f(0)=1,n=1,也只有一种情况,f(1)=1,当数组数目大于1,构成的BST树是这样的:以i为根节点,左子树是1..i-1构成的,右边是i+1..n构成的,有多少种情况呢,以i为根节点,情况是:f(i-1)*f(n-i)种,i可取1、2、… n,因此,$f(n)=\sum\limits_{i=1}^{n}f(i-1)*f(n-i)$,至此,就得到动态规划的公式了。

解决方案1(C++)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 k = 1; k <= i; k++) {
f[i] += f[k-1] * f[i-k];
}
}
return f[n];
}
};

解决方案2(Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[-1]

其实,不用递归也是可以的,这个问题与卡塔兰数有关,一般的数据结构书上也有公式说明。

1
2
3
4
5
6
7
8
9
import math
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
return math.factorial(2*n)/(math.factorial(n+1)*math.factorial(n))

相关问题


(M) Unique Binary Search Trees II

题目来源