1. Description
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
2. Example
Example 1
Input: 3
Output: 5
3. Constraints
4. Solutions
Dynamic Programming
Catalan number
Time complexity: O(1)
Space complexity: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // for each n, we could let the root be any number in the range [1, n]
// after determining the root, the nodes of left subtree and the right subtree are also determined
// but subtree also have lots of style, so we need to multiple the left subtree's possible styles and the right subtree's possible styles
// this question is the definition of Catalan number
// we could get the result just using math
class Solution
{
public:
// int numTrees(int n)
int numTrees(const int i_nodeCount)
{
long long int result = 1;
for(int i = 0; i < i_nodeCount; i++)
{
result = result * 2*(2*i+1) / (i+2);
}
return result;
}
};
|
Dynamic Programming
Time complexity: O(1)
Space complexity: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| // also, we could solve the question by dynamic programming
class Solution
{
public:
// int numTrees(int n)
int numTrees(int n)
{
vector<int> possibleStyleCount(n + 1); // add 0 node to simplify the calculation
possibleStyleCount[0] = possibleStyleCount[1] = 1;
for(int i = 2; i <= n; i++)
{
for(int j = 0; j < i; j++)
{
possibleStyleCount[i] += possibleStyleCount[j] * possibleStyleCount[i - j - 1];
// nodes count = left subtree's node + root + right subtree's node
// so if the right subtree has j nodes, right subtree has i-j-1 nodes
}
}
return possibleStyleCount[n];
}
};
|