# 894. All Possible Full Binary Trees

full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with `N`nodes.  Each element of the answer is the root node of one possible tree.

Each `node` of each tree in the answer must have `node.val = 0`.

You may return the final list of trees in any order.

Example 1:

``````Input: 7
Output: [[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]]
Explanation:
``````

Note:

• `1 <= N <= 20`

``````    0
/ \
0   0
/ \
0   0

0
/ \
0   0
/ \
0   0
``````

``````class Solution {
public:
vector<TreeNode*> allPossibleFBT(int N) {
if (N % 2 == 0) return {};
if (N == 1) return {new TreeNode(0)};
vector<TreeNode*> res;
for (int i = 1; i < N; i += 2) {
vector<TreeNode*> left = allPossibleFBT(i), right = allPossibleFBT(N - i - 1);
for (auto a : left) {
for (auto b : right) {
TreeNode *cur = new TreeNode(0);
cur->left = a;
cur->right = b;
res.push_back(cur);
}
}
}
return res;
}
};
``````

``````class Solution {
public:
unordered_map<int, vector<TreeNode*>> m;
vector<TreeNode*> allPossibleFBT(int N) {
if (N % 2 == 0) return {};
if (N == 1) return {new TreeNode(0)};
if (m.count(N)) return m[N];
vector<TreeNode*> res;
for (int i = 1; i < N; i += 2) {
vector<TreeNode*> left = allPossibleFBT(i), right = allPossibleFBT(N - i - 1);
for (auto a : left) {
for (auto b : right) {
TreeNode *cur = new TreeNode(0);
cur->left = a;
cur->right = b;
res.push_back(cur);
}
}
}
return m[N] = res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/894

Unique Binary Search Trees II