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.

&nbsp;
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]]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 20


We can't create Full Binary tree with even number of nodes. e.g n = 2/4/6/8...
start with cache having n = 1
	cache = {1:TreeNode()}
	
	n = 3
							0 (root)
						 1     1
	n = 5       
	                        0 (root1)                  0 (root2) 
						 1     3                     3    1
	n = 7  
	                         0                    0                   0
						 1      5              3    3              5     1


class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        def helper(n):
            if n in cache:
                return cache[n]
            # We use result array to store all possible binary tree of size n
            result = [] 
            leftNodes, rightNodes = 1,n-2
            # if n = 7 then, (leftNodes,rightNodes) should be : (1,5),(3,3),(5,1) 
            while rightNodes >0:
                root = TreeNode()
                if leftNodes not in cache:
                    helper(leftNodes)
                if rightNodes not in cache:
                    helper(rightNodes)
                leftTree = cache[leftNodes]
                rightTree = cache[rightNodes]
                # Using two for loops we generate all possible binary tree.
                # Always remember root of each binary tree is diffrent, So create new root every time
                for i in range(len(leftTree)):
                    for j in range(len(rightTree)):
                        root.left = leftTree[i]
                        root.right = rightTree[j]
                        result.append(root)
                        root = TreeNode()
                leftNodes += 2
                rightNodes -= 2
            cache[n] = result
            return result
            
        if n % 2 == 0:
            return 
        else:
            cache = {1:[TreeNode()]}
            return helper(n)
			
Thank You 😊
class Solution {
    List<TreeNode>[] memo;
    public List<TreeNode> allPossibleFBT(int n) {
        memo = new ArrayList[n+1];
        return dp(n);
    }

    public List<TreeNode> dp(int n){
        if(n==0 || n==2){
            return new ArrayList<TreeNode>();
        }
        if(n==1){
            List<TreeNode> temp = new ArrayList<>();
            temp.add(new TreeNode(0));
            return temp;
        }
        List<TreeNode> res = new ArrayList<>();
        for(int i=1;i<n-1;i=i+2){
            List<TreeNode> right;
            List<TreeNode> left;
            if(memo[i]!=null) right = memo[i];
            else right = dp(i);
            if(memo[n-1-i]!=null) left = memo[n-1-i];
            else left = dp(n-1-i);

            for(TreeNode l : left){
                for(TreeNode r : right){
                    TreeNode temp = new TreeNode(0);
                    temp.left=l;
                    temp.right=r;
                    res.add(temp);
                }
            }
         }
        memo[n] = res;
        return res;

    }
}
class Solution {
public:
    unordered_map<int,vector<TreeNode*>> dp;
    int hash(int i,int j){
        return (i*21 + j);
    }
    vector<TreeNode*> fn(int l,int r){
        int has = hash(l,r);
        if(dp.find(has)!=dp.end()){
            return dp[has];
        }
        vector<TreeNode*> res;
        if(r<l){
            return {NULL};
        }
        if(r==l){
            return {new TreeNode(0)};
        }
        for(int i = l+1;i<r;i++){
             vector<TreeNode*> left =  fn(l,i-1);
            vector<TreeNode*> right =  fn(i+1,r);
              for(auto le:left){
                for(auto ri:right ){
                    TreeNode* temp = new TreeNode(0);
                    temp->left = le;
                    temp->right = ri;
                    res.push_back(temp);
                }
            }
        }
        return dp[has] = res;
    }
    vector<TreeNode*> allPossibleFBT(int n) {
        return fn(1,n);
    }
var allPossibleFBT = function(n) {
    if(n % 2 == 0) return [];
    if( n == 1 ) return [new TreeNode(0)];
    const ans = [];

    const generate = (x) => {
        if(x == 1) return [new TreeNode(0)];
        const ans = [];
        for(let l = 1; l <= x - 2; l += 2) {
            const left = generate(l);
            const right = generate(x - 1 - l);
            left.forEach(l => {
                right.forEach(r => {
                    const root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    ans.push(root);
                });
            });
        }
        return ans;
    }

    for(let l = 1; l <= n - 2; l += 2) {
        const left = generate(l);
        const right = generate(n - 1 - l);
        left.forEach(l => {
            right.forEach(r => {
                const root = new TreeNode(0);
                root.left = l;
                root.right = r;
                ans.push(root);
            });
        });
    }

    return ans;
};
All Possible Full Binary Trees