Leetcode题解
Search…
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必须是奇数。
可以创建一个数组保存已有的满二叉树，不需要递归。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
vector<vector<TreeNode*>>allPath;
12
public:
13
vector<TreeNode*> allPossibleFBT(int N) {
14
vector<TreeNode*> res;
15
if(N%2==0) return res;
16
TreeNode* zero = new TreeNode(0);
17
res.push_back(zero);
18
allPath.push_back(res);
19
20
if(N/2+1 <= allPath.size()) return allPath[N/2];
21
int len=allPath.size();
22
for(int i=len;i<N/2+1;i++)
23
{
24
vector<TreeNode*>tmp;
25
// cout<<count<<endl;
26
for(int j=0;j<i;j++)
27
{
28
for(auto l : allPath[j])
29
for(auto r: allPath[i-1-j])
30
{
31
TreeNode* root = new TreeNode(0);
32
root->left = l;
33
root->right = r;
34
tmp.push_back(root);
35
}
36
}
37
allPath.push_back(tmp);
38
}
39
40
//cout<<res.size()<<endl;
41
42
return allPath[N/2];
43
}
44
};
Copied!
执行用时 :132 ms, 在所有 C++ 提交中击败了96.42%的用户 内存消耗 :20.8 MB, 在所有 C++ 提交中击败了90.36%的用户
Last modified 5mo ago
Copy link