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

Return a list of all possible full binary trees withNnodes. Each element of the answer is the root node of one possible tree.

Eachnodeof each tree in the answer must havenode.val = 0.

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        if(N % 2 == 0)
            return res;

        if(N == 1) {
            res.add(new TreeNode(0));
            return res;
        }

        for(int i = 1; i <= N - 2; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(N - 1 - i);

            for(TreeNode l: left) {
                for(TreeNode r: right) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }

        return res;
    }
}