266. Tree Shapes
An archivist stores n records under the keys 1, 2, ..., n in a binary search tree, but she is free to insert the keys in any order she likes. Two trees are the same shape if one can be turned into the other without looking at the key values, that is, the pattern of left and right children is identical.
Return the number of structurally different binary search trees that can hold the n keys. By convention an empty tree counts as one shape, so the answer for n = 0 is 1. The result fits in a 32-bit integer for the allowed n. Use a dynamic programme over the number of nodes in the left subtree, O(n^2) time and O(n) space.
Example 1
- Input:
- n = 6
- Output:
- 132
- Explanation:
Six keys can form 132 different tree shapes.
Example 2
- Input:
- n = 0
- Output:
- 1
- Explanation:
The empty tree is counted as one shape.
Constraints
0 ≤ n ≤ 19
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n^2)
- Space
- O(n)