// Runtime: 5 ms, faster than 35.54% of Java online submissions for All Possible Full Binary Trees.
// Memory Usage: 48.8 MB, less than 30.77% of Java online submissions for All Possible Full Binary Trees.
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> results = new ArrayList<>();

        if (N % 2 == 0) return results;

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

        for (int i = 1; i <= N - 2; i += 2) {
            for (TreeNode left: allPossibleFBT(i))
                for (TreeNode right: allPossibleFBT(N - 1 - i)) {
                    TreeNode r = new TreeNode(0);
                    r.left = left;
                    r.right = right;
                    results.add(r);
                }
        }

        return results;
    }
}