满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
示例输入：7 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]] 解释：
提示1 <= N <= 20
解读一、先明确下，只要当N为奇数时，才有对应的结果存在。 不然都为空。首先要有一个根结点，要保存是满二叉树，每个结点下面只有0个或2个结点。这个也可以由算法自己演算出来。
二、n个结点的满二叉树 = （n-2)结点的满二叉树叶子结点增加2个子结点的所有情况。
三、由上面可知，可采用递归的方法处理。
四、每种(n-2)结点的满二叉树叶子结点增加子结点的所有情况，可能会有重复的情况，因此还得去下重复树。
代码// 判断相同树
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p != null && q != null && p.val == q.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } return false; }// 计算树的所有叶子，这里只针对满二叉树
public void addleafs(TreeNode node, List<TreeNode> leafs) { if (node == null) { return; } if (node.left == null && node.right == null) { leafs.add(node); return; } addleafs(node.left, leafs); addleafs(node.right, leafs); }// 产生叶子结点增加二个子结点的新树
public TreeNode createTree(TreeNode node, TreeNode target) { if (node == null) { return null; } TreeNode tn = new TreeNode(node.val); if (node == target) { tn.left = new TreeNode(0); tn.right = new TreeNode(0); } else { tn.left = createTree(node.left, target); tn.right = createTree(node.right, target); } return tn; }// 递归处理
public void goNext(List<TreeNode> root, int N, int k) { if (k == N) { rList = new ArrayList<>(root); return; } if (k == 0) { List<TreeNode> next = new ArrayList<>(); next.add(new TreeNode(0)); goNext(next, N, k + 1); return; } if (k > N || k == N - 1) { return; } List<TreeNode> tmps = new ArrayList<>(); for (int i = 0; i < root.size(); i++) { TreeNode tmpNode = root.get(i); List<TreeNode> leafs = new ArrayList<>(); addleafs(tmpNode, leafs); for (int j = 0; j < leafs.size(); j++) { TreeNode pTree = createTree(tmpNode, leafs.get(j)); boolean isSame = false; for (TreeNode treeNode : tmps) { if (isSameTree(pTree, treeNode)) { isSame = true; break; } } if (!isSame) { tmps.add(pTree); } } } goNext(tmps, N, k + 2); }// 主函数及全局变量
List<TreeNode> rList = new ArrayList<>(); public List<TreeNode> allPossibleFBT(int N) { goNext(null, N, 0); return rList; }
