所有可能的满二叉树

894. 所有可能的满二叉树

满二叉树是一类二叉树，其中每个结点恰好有 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]]

解题思路：

本题要求给出所有满二叉树，那么自然要想到递归构造，题中给出函数 allPossibleFBT(int N)

对于递归，我们首先要想到两点

确认递归目的
确认递归出口

确认递归目的：令allPossibleFBT(int N)意义为，所有含N个节点的满二叉树列表

确认递归出口：通过简单的逻辑和计数，我们知道有三点

第一，我们要使用一个Map来存储和N对应的二叉树列表，以此作为出口，如果当前map已经包含了对应的值
Map<Integer, List<TreeNode>> map = new HashMap();
if(!map.containsKey(N))
那么这里就是递归出口，直接退出
第二，我们发现所有的满二叉树必定有着奇数个的节点，那么我们可以在函数中进行判断，只有是奇数个数，才继续往下执行程序，否则直接退出
else if(N%2 == 1)
第三，如果N == 1，即只有一个节点，那么我们直接添加一个值为0的节点，放入列表即可
if(N == 1){ ans.add(new TreeNode(0)); }

那么由以上两点，我们可以确认递归思路

首先，进行出口判断，然后调用函数allPossibleFBT(int N)，这个函数调用2次，第一次参数为x，第二次为y，这里设置一个循环，0 =< x < N

然后 y = N - 1 - x 即 allPossibleFBT(x) allPossibleFBT(y)，分别代表存放着 所有满足条件的左子树的集合 和 所有满足条件的右子树的集合

而 ``allPossibleFBT(N)`即表示 节点数为N时，所有满足条件的树的root集合

那么我们对这两个函数的成员循环取值，定义一个节点，节点左边指向左子树集合的成员，右边指向右子树集合的成员，通过for循环轮回遍历，就可以取得所有符合条件的树，最后进行返回即可

AC代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, List<TreeNode>> map = new HashMap();
    public List<TreeNode> allPossibleFBT(int N) {
        //通过map缓存之前的计算结果，这样我们可以优化时间复杂度，不必在递归中再次计算他们
        if(!map.containsKey(N)){
            List<TreeNode> ans = new LinkedList<>();
            if(N == 1){
                ans.add(new TreeNode(0));
            }else if(N%2 == 1){
                for(int x = 0;x < N;x++){
                    int y = N - 1 - x;
                    //通过for循环遍历所有左子树的成员和右子树成员
                    //在函数体内部创建新的树，这样就可以得到所有满足条件的树
                    for(TreeNode left : allPossibleFBT(x))
                        for(TreeNode right : allPossibleFBT(y)){
                            TreeNode node = new TreeNode(0);
                            node.left = left;
                            node.right = right;
                            ans.add(node);
                        }
                }
            }
            map.put(N,ans);
        }
        return map.get(N);
    }
    
}