## Algorithm

Problem Name: 894. All Possible Full Binary Trees

Given an integer `n`, return a list of all possible full binary trees with `n` nodes. Each node of each tree in the answer must have `Node.val == 0`.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

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

Example 1:

```Input: n = 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]]
```

Example 2:

```Input: n = 3
Output: [[0,0,0]]
```

Constraints:

• `1 <= n <= 20`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<TreeNode*> allPossibleFBT(int N) {
vector<TreeNode*> res;
if (N == 1) {
res.push_back(new TreeNode(0));
return res;
}
--N;
for (int i = 1; i  <  N; i += 2) {
auto left = allPossibleFBT(i);
auto right = allPossibleFBT(N - i);
for (TreeNode* l: left) {
for (TreeNode* r: right) {
TreeNode* cur = new TreeNode(0);
cur->left = l;
cur->right = r;
res.push_back(cur);
}
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
n = 7

Output

cmd
[[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]]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List allPossibleFBT(int n) {
Map();
return allPossibleFBTHelper(n, dp);
}

private List < TreeNode> allPossibleFBTHelper(int n, Map result = new ArrayList<>();
if (n == 1) {
} else if (n % 2 == 1) {
for (int i = 0; i  <  n; i++) {
int j = n - 1 - i;
for (TreeNode left : allPossibleFBTHelper(i, dp)) {
for (TreeNode right : allPossibleFBTHelper(j, dp)) {
TreeNode root = new TreeNode(0);
root.left = left;
root.right = right;
}
}
}
}
dp.put(n, result);
return dp.get(n);
}
}
``````
Copy The Code &

Input

cmd
n = 7

Output

cmd
[[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]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const allPossibleFBT = function(N) {
if (N <= 0) return []
const dp = Array.from({ length: N + 1 }, () => [])
dp[1].push(new TreeNode(0))

for (let numNode = 1; numNode  < = N; numNode += 2) {
for (let leftNode = 1; leftNode  <  numNode; leftNode += 2) {
for (let left of dp[leftNode]) {
for (let right of dp[numNode - 1 - leftNode]) {
let root = new TreeNode(0)
root.left = left
root.right = right
dp[numNode].push(root)
}
}
}
}
return dp[N]
};
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
[[0,0,0]]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def allPossibleFBT(self, N):
def constr(N):
if N == 1: yield TreeNode(0)
for i in range(1, N, 2):
for l in constr(i):
for r in constr(N - i - 1):
m = TreeNode(0)
m.left = l
m.right = r
yield m
return list(constr(N))
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
[[0,0,0]]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0894_AllPossibleFullBinaryTrees
{
public IList < TreeNode> AllPossibleFBT(int N)
{
var cache = new Dictionary<int, IList AllPossibleFBT(int n, Dictionary<int, IList();
if (cache.ContainsKey(n)) return cache[n];
if (n == 1)
{
cache[n] = new List < TreeNode>() { new TreeNode(0) };
return cache[n];
}

var results = new List < TreeNode>();
for (int left = 1; left  <  n; left += 2)
{
int right = n - 1 - left;
foreach (var leftNode in AllPossibleFBT(left))
foreach (var rightNode in AllPossibleFBT(right))
{
var root = new TreeNode(0);
root.left = leftNode;
root.right = rightNode;
}
}

cache[n] = results;
return cache[n];
}
}
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
[[0,0,0]]