// Runtime: 1 ms, faster than 100.00% of Java online submissions for All Possible Full Binary Trees.
// Memory Usage: 43.6 MB, less than 100.00% of Java online submissions for All Possible Full Binary Trees.
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0) return new ArrayList<TreeNode>();

        return list(N, new List[N + 1]);
    }

    private List<TreeNode> list(int N, List<TreeNode>[] dp) {
        if (dp[N] != null) return dp[N];

        List<TreeNode> results = new ArrayList<>();

        if (N > 1) {
            for (int i = 1; i <= N - 2; i += 2) {
                for (TreeNode left: list(i, dp))
                    for (TreeNode right: list(N - 1 - i, dp)) {
                        TreeNode r = new TreeNode(0);
                        r.left = left;
                        r.right = right;
                        results.add(r);
                    }
            }
        } else {
            results.add(new TreeNode(0));
        }

        dp[N] = results;
        return results;
    }
}