[leetcode] problem 894 – all possible full binary trees

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

private Map<Integer, List<TreeNode>> map = new HashMap<>();

public List<TreeNode> allPossibleFBT(int N) {
    List<TreeNode> result = new ArrayList<>();

    if (N == 1) {
        result.add(new TreeNode(0));
        return result;
    }
    else if (N % 2 == 0)
        return result;

    if (map.containsKey(N))
        return map.get(N);
    
    for (int i = 1; i < N; i += 2) {
        List<TreeNode> left = allPossibleFBT(i);
        List<TreeNode> right = allPossibleFBT(N - i - 1);

        for (TreeNode l : left) {
            for (TreeNode r : right) {
                TreeNode root = new TreeNode(0);
                root.left = l;
                root.right = r;
                result.add(root);
            }
        }
    }
    
    map.put(N, result);
    
    return result;
}