894.All Possible Full Binary Trees

894.All Possible Full Binary Trees

难度:Medium

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

fivetrees.png

提示： 1 <= N <= 20

每个满二叉树的左右子树必须是满二叉树，所以对于一个满二叉树来说，N的所有满二叉树可以有x的满二叉树和(N-X)的满二叉树作为左右子树构成。N必须是奇数。 可以创建一个数组保存已有的满二叉树，不需要递归。

/**
 * 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 {
vector<vector<TreeNode*>>allPath;
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        vector<TreeNode*> res;
        if(N%2==0) return res;
        TreeNode* zero = new TreeNode(0);
        res.push_back(zero);
        allPath.push_back(res);

        if(N/2+1 <= allPath.size()) return allPath[N/2];
        int len=allPath.size();
        for(int i=len;i<N/2+1;i++)
        {
            vector<TreeNode*>tmp;
            // cout<<count<<endl;
            for(int j=0;j<i;j++)
            {
                for(auto l : allPath[j])
                for(auto r: allPath[i-1-j])
                {
                TreeNode* root = new TreeNode(0);
                root->left = l;
                root->right = r;
                tmp.push_back(root);
                }
            }
            allPath.push_back(tmp);
        }

        //cout<<res.size()<<endl;

        return allPath[N/2];
    }
};

执行用时 :132 ms, 在所有 C++ 提交中击败了96.42%的用户 内存消耗 :20.8 MB, 在所有 C++ 提交中击败了90.36%的用户