1045. All Full Trees
A circuit designer lays out switching networks where every switch either ends the line or splits it into exactly two branches. Given the integer n, list every distinct network with exactly n switches, modelled as a binary tree where each node has either zero or two children. Every node value is 0.
Return the root of each distinct tree in a list. Trees that differ in shape are different; the order of the returned list does not matter. If no such tree exists, return an empty list. For judging, each tree is written in level-order with null for missing children.
Reuse the lists of smaller sizes instead of rebuilding them for every pairing.
Example 1
- Input:
- n = 3
- Output:
- [[0,0,0]]
- Explanation:
Only one shape exists: a root with two leaf children.
Example 2
- Input:
- n = 5
- Output:
- [[0,0,0,null,null,0,0],[0,0,0,0,0]]
- Explanation:
The root's two subtrees have sizes 1 and 3 or 3 and 1, giving two distinct trees.
Example 3
- Input:
- n = 4
- Output:
- []
- Explanation:
An even node count is impossible because each split adds two nodes, so the list is empty.
Constraints
1 ≤ n ≤ 11
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/2) * n)
- Space
- O(C(n/2) * n) including the output