894. All Possible Full Binary Trees

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with `N` nodes.  Each element of the answer is the root node of one possible tree.

Each `node` of each tree in the answer must have `node.val = 0`.

You may return the final list of trees in any order.

Example 1:

```Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

```

Note:

• `1 <= N <= 20`

894. All Possible Full Binary Trees
``````struct Solution;
use rustgym_util::*;

impl Solution {
fn all_possible_fbt(n: i32) -> Vec<TreeLink> {
if n % 2 == 0 {
return vec![];
}
if n == 1 {
vec![tree!(0)]
} else {
let mut res = vec![];
let mut l = 1;
let mut r = n - 1 - l;
while r > 0 {
let left_trees = Self::all_possible_fbt(l);
let right_trees = Self::all_possible_fbt(r);
for left in &left_trees {
for right in &right_trees {
res.push(tree!(0, left.clone(), right.clone()));
}
}
r -= 2;
l += 2;
}
res
}
}
}

#[test]
fn test() {
let n = 7;
let res = [
tree!(
0,
tree!(0),
tree!(0, tree!(0), tree!(0, tree!(0), tree!(0)))
),
tree!(
0,
tree!(0),
tree!(0, tree!(0, tree!(0), tree!(0)), tree!(0))
),
tree!(
0,
tree!(0, tree!(0), tree!(0)),
tree!(0, tree!(0), tree!(0))
),
tree!(
0,
tree!(0, tree!(0), tree!(0, tree!(0), tree!(0))),
tree!(0)
),
tree!(
0,
tree!(0, tree!(0, tree!(0), tree!(0)), tree!(0)),
tree!(0)
),
];
assert_eq!(Solution::all_possible_fbt(n), res);
}
``````