所有可能的满二叉树

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

　　code：把结点总数拆分为：左、根、右进行递归。如7可以拆为1（左）、1（根）、5（右），此时5又可以拆为左（1）、根（1）、右（3），无论怎样拆，都要保证根节点数是1既可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<int,vector<TreeNode*>> hash;//1.作为缓存优化
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if(N<=0||N&1==0)//2.偶数无法组成满二叉树
            return {};
        
        vector<TreeNode*> res;
        if(N==1)
        {
            TreeNode* head=new TreeNode(0);
            res.push_back(head);
            return res;
        }
        for(int i=1;i<N;i+=2)//3.每次加2，因为要跳过根节点
        {
            vector<TreeNode*> left;
            unordered_map<int,vector<TreeNode*>>::iterator pos=hash.find(i);
            if(pos==hash.end())
            {
                left=allPossibleFBT(i);//4.左子树中结点的个数
                hash.insert({i,left});
            }
            else
                left=hash[i];

            vector<TreeNode*> right;
            pos=hash.find(N-i-1);
            if(pos==hash.end())
            {
                right=allPossibleFBT(N-i-1);//5.右子树中结点的个数,减去根节点
                hash.insert({N-1-i,right});
            }
            else
                right=hash[N-i-1];

            for(auto l:left)
            {
                for(auto r:right)
                {
                    TreeNode* head=new TreeNode(0);
                    head->left=l;
                    head->right=r;
                    res.push_back(head);
                }
            }
        }
        return res;
    }
};