All Possible Full Binary Trees

A full binary tree is a binary tree in which each node has either no children or exactly two children.

Given n, return the roots of all structurally distinct full binary trees with exactly n nodes. Every node must have value 0. Return each valid structure once, in any order. If no such tree exists, return an empty list.

The examples show each tree in level order, using null for missing children and omitting trailing nulls.

Example 1:

Input: n = 2

Output: []

Explanation: A two-node tree would have a node with exactly one child, so no full binary tree exists.

Example 2:

Input: n = 3

Output: [[0,0,0]]

Explanation: The root must have two leaf children. All three nodes have value 0, and there is only one possible structure.

Example 3:

Input: n = 5

Output: [
  [0,0,0,0,0],
  [0,0,0,null,null,0,0]
]

Explanation: The root has two children. One child must be a leaf, and the other must have two leaf children. Either the left or the right child can be the three-node subtree, giving two structures.

Constraints:

• 1 <= n <= 20