# 96. Unique Binary Search Trees 不同的二叉搜索树

@TOC

## # 题目描述

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
``````

## # 解题方法

### # 记忆化递归

``````class Solution(object):
def __init__(self):
self.dp = dict()

def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n in self.dp:
return self.dp[n]
if n == 0 or n == 1:
return 1
ans = 0
for i in range(1, n + 1):
ans += self.numTrees(i - 1) * self.numTrees(n - i)
self.dp[n] = ans
return ans
``````

``````class Solution {
public:
int numTrees(int n) {
if (n == 0) return 1;
if (m_.count(n)) return m_[n];
int res = 0;
for (int i = 0; i < n; i++) {
int left = numTrees(i);
int right = numTrees(n - 1 - i);
res += left * right;
}
return m_[n] = res;
}
private:
unordered_map<int, int> m_;
};
``````

### # 动态规划

``````给定一个数n，求1到n这些数可以构成多少棵二叉树。

G(n)：长度为n的序列的所有唯一的二叉树。

F(i,n)，1<=i<=n：以i作为根节点的二叉树的数量。

G(n)就是我们要求解的答案，G(n)可以由F(i,n)计算而来。

G(n)=F(1,n)+F(2,n)+...+F(n,n)                           (1)

G(0)=1,G(1)=1

F(i,n)=G(i-1)*G(n-i) 1<=i<=n                            (2)

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

``````

``````class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1, 1]
for i in xrange(2, n + 1):
count = 0
for j in xrange(i):
count += dp[j] * dp[i - j - 1]
dp.append(count)
return dp.pop()
``````

``````class Solution {
public:
int numTrees(int n) {
// how many trees if the total tree has dp[i] nodes.
vector<int> dp(n + 1);
dp[0] = dp[1] = 1;
for (int i = 2; i < n + 1; i ++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
};
``````

### # 卡特兰数

`h(0)=1,h(1)=1`，卡塔兰数数满足递归式：

`h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0)` (其中n>=2)这是n阶递归关系;

`h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)`

``````class Solution {
public:
int numTrees(int n) {
// how many trees if the total tree has dp[i] nodes.
long long res = 1;
for (int i = n + 1; i <= 2 * n; i++) {
res = res * i / (i - n);
}
return res / (n + 1);
}
};
``````

``````class Solution {
public:
int numTrees(int n) {
// how many trees if the total tree has dp[i] nodes.
vector<int> dp = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190};
return dp[n];
}
};
``````

## # 日期

2018 年 2 月 25 日 2018 年 12 月 31 日 —— 2018年最后一天！