894. 所有可能的真二叉树

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

输入：n = 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]]
示例 2：

输入：n = 3
输出：[[0,0,0]]

class Solution {
public:
    map> ma;
    vector allPossibleFBT(int n) {
        //计算特殊情况，其中0，1，2，>2
        if(n==0||n==2){
            return {};
        }else if(n==1){
            return {new TreeNode(0)};
        }
        if(ma.count(n)!=0)
        {
            return ma[n];
        }
        vector ret;
        //分类计算，首先计算左节点，然后计算右节点，最后合并，其中左节点的种类为从1开始统计
        for(int i = 0;i
            vector left= allPossibleFBT(i);
            vector right = allPossibleFBT(n-i-1);//1为根节点
            for(TreeNode* l:left)//一共的可能性是左子树*右子树,但是出现重复计算，其中左子树会和右子树重复
            {
                for(TreeNode* r:right){
                    TreeNode* root = new TreeNode(0);
                    root->left = l;
                    root->right = r;
                    ret.push_back(root);
                }
            }
        }
        ma[n] = ret;
        return ret;
    }
};