1044. Every Tree Shape
A records office files cards numbered 1 to n in a binary search tree, and an auditor wants to inspect every distinct way those cards could be arranged. Given the integer n, build every structurally unique binary search tree that holds each value from 1 to n exactly once and return the root of each one in a list.
Two trees are different when their shapes differ, so no tree may be reported twice. The order of the returned trees does not matter. For judging, every tree is written in level-order with null for an absent child.
Aim for time proportional to the total output size by never rebuilding the same value range twice.
Example 1
- Input:
- n = 2
- Output:
- [[1,null,2],[2,1]]
- Explanation:
Root 1 can only have 2 on its right, and root 2 can only have 1 on its left, giving two shapes.
Example 2
- Input:
- n = 3
- Output:
- [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
- Explanation:
Each of the three possible roots splits the other keys into left and right ranges, giving five distinct shapes in total.
Constraints
1 ≤ n ≤ 6
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(C(n) * n), C(n) = nth Catalan number
- Space
- O(C(n) * n) including the output