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%的用户
Last modified 1yr ago