# [leetcode题解]96. Unique Binary Search Trees

```1     1       2       3   3
\     \     / \     /   /
3     2   1   3   2   1
/ 		 \         /     \
2         3       1       2
```

```1      2
\    /
2  1
```

f(2) = f(0) + f(1) ，1 为根的情况f(1) = f(0) ，2 为根的情况

f(3) = f(0) + f(2) ，1 为根的情况
f(3) += f(1) + f(1) ，2 为根的情况
f(3) += f(2) + f(0) ，3 为根的情况

f(i) =f(k − 1) × f(i − k) k=1…i

leetcode题目如下：
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
```

```#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
int numTrees(int n) {
int *res = new int[n + 1];
res[0] = res[1] = 1;
for (int i = 2; i <= n; ++i)
{
res[i] = 0;
for (int j = 0; j < i; ++j)
{
res[i] += res[j] * res[i - 1 - j];
}
}
int t = res[n];
delete[] res;
return t;
}
};

int main()
{
Solution so;
int n = so.numTrees(3);

cout << n << endl;

return 0;
}
```