# 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

TreeNode *copyTree(TreeNode *root) {
if (root == nullptr) return nullptr;
TreeNode *res = new TreeNode(0);
res->left = copyTree(root->left);
res->right = copyTree(root->right);
return res;
}

vector allPossibleFBT(int N) {
vector res;
if (N % 2 == 0) return res;

vector<vector> dp(N+1);
dp[1].push_back(new TreeNode(0));

for(int i = 1;i < dp.size();i+=2) {
// dp[i];
for(int j = 1;j < i;j+=2) {
vector &left = dp[j];
vector &right = dp[(i-j-1)];
for(auto &l: left) {
for(auto &r: right) {
TreeNode *node = new TreeNode(0);
node->left = copyTree(l);
node->right = copyTree(r);
dp[i].push_back(node);
}
}
}
}
return dp[N];
}


vector &allPossibleFBT(int N, vector<vector> &cache) {
if (cache[N].size() != 0) return cache[N];

for(int i = 1;i < N;i++) {
vector &left = allPossibleFBT(i, cache);
vector &right = allPossibleFBT(N - i - 1, cache);
for(auto l: left) {
for(auto r: right) {
TreeNode *node = new TreeNode(0);
node->left = l;
node->right = r;
cache[N].push_back(node);
}
}
}
return cache[N];
}

vector allPossibleFBT(int N) {
vector res;
if (N % 2 == 0) return {};
vector<vector> cache(21);

cache[1].push_back(new TreeNode(0));
return allPossibleFBT(N, cache);
}


vector allPossibleFBT(int N) {
vector res;
if (N % 2 == 0) return res;

vector<vector> dp(N+1);
dp[1].push_back(new TreeNode(0));

for(int i = 1;i < dp.size();i+=2) {
// dp[i];
for(int j = 1;j left = copyTree(l);
node->right = copyTree(r);
dp[i].push_back(node);
}
}
}
}
return dp[N];
}


vector allPossibleFBT(int N) {
vector res;
if (N % 2 == 0) return res;

vector<vector> dp(N+1);
dp[1].push_back(new TreeNode(0));

for(int i = 1;i < dp.size();i+=2) {
// dp[i];
for(int j = 1;j left = l;//copyTree(l);
node->right = r;//copyTree(r);
dp[i].push_back(node);
}
}
}
}
return dp[N];
}