/*
https://leetcode.com/problems/all-possible-full-binary-trees/
Runtime: 1 ms, faster than 100.00% of Java online submissions for All Possible Full Binary Trees.
Memory Usage: 40.1 MB, less than 100.00% of Java online submissions for All Possible Full Binary Trees.
*/
class Solution {
    private static final Cache CACHE = new Cache();

    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> ans = CACHE.tries[N];
        if (ans == null) {
            ans = new ArrayList<>();
            for (int l = 1, r = N - 2; r > 0; l += 2, r -= 2) {
                for (TreeNode left : allPossibleFBT(l))
                for (TreeNode right : allPossibleFBT(r)) {
                    TreeNode node = new TreeNode(0);
                    node.left = left;
                    node.right = right;
                    ans.add(node);
                }
            }
            CACHE.tries[N] = ans;
        }
        return ans;
    }

    private static class Cache {
        private List<TreeNode>[] tries = new List[21];

        public Cache() {
            tries[1] = Arrays.asList(new TreeNode(0));
        }
    }
}