解法一：递归

每一棵满二叉树的左右子树都是满二叉树。
用Map保存子问题的解和对偶数情况做剪枝参考官方题解：https://leetcode-cn.com/problems/all-possible-full-binary-trees/solution/suo-you-ke-neng-de-man-er-cha-shu-by-leetcode/

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     Map<Integer, List<TreeNode>> map = new HashMap<>();
  13.     public List<TreeNode> allPossibleFBT(int N) {
  14.         if (!map.containsKey(N)) {
  15.             List<TreeNode> list = new LinkedList<>();
  16.             if (N == 1) {
  17.                 TreeNode root = new TreeNode(0);
  18.                 list.add(root);
  19.             } else if (N % 2 == 1) {
  20.                 for (int x = 0; x <= N - 1; ++x) {
  21.                     int y = N - 1 - x;
  22.                     for (TreeNode left : allPossibleFBT(x)) {
  23.                         for (TreeNode right : allPossibleFBT(y)) {
  24.                             TreeNode root = new TreeNode(0);
  25.                             root.left = left;
  26.                             root.right = right;
  27.                             list.add(root);
  28.                         }
  29.                     }
  30.                 }
  31.             }
  32.             map.put(N, list);
  33.         }
  34.         return map.get(N);
  35.     }
  36. }