/*
Runtime: 2 ms, faster than 94.60% of Java online submissions for All Possible Full Binary Trees.
Memory Usage: 42.1 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 & 1) == 0) return Collections.emptyList();
        List<TreeNode>[] dp = new List[N + 1];
        dp[1] = Arrays.asList(new TreeNode(0));
        for (int i = 3; i <= N; i += 2) {
            List<TreeNode> ans = dp[i] = new ArrayList<>();
            for (int l = 1, r = i - 2; r > 0; l += 2, r -= 2) {
                for (TreeNode left : dp[l])
                for (TreeNode right : dp[r]) {
                    TreeNode node = new TreeNode(0);
                    node.left = left;
                    node.right = right;
                    ans.add(node);
                }
            }
        }
        return dp[N];
    }
}