• Time:O(2^n)
• Space:O(2^n)

## C++

``````class Solution {
public:
vector<TreeNode*> allPossibleFBT(int n) {
if (n % 2 == 0)
return {};
if (n == 1)
return {new TreeNode(0)};
if (memo.count(n))
return memo[n];

vector<TreeNode*> ans;

for (int leftCount = 0; leftCount < n; ++leftCount) {
const int rightCount = n - 1 - leftCount;
for (TreeNode* left : allPossibleFBT(leftCount))
for (TreeNode* right : allPossibleFBT(rightCount)) {
ans.push_back(new TreeNode(0));
ans.back()->left = left;
ans.back()->right = right;
}
}

return memo[n] = ans;
}

private:
unordered_map<int, vector<TreeNode*>> memo;
};
``````

## JAVA

``````class Solution {
public List<TreeNode> allPossibleFBT(int n) {
if (n % 2 == 0)
return new ArrayList<>();
if (n == 1)
return Arrays.asList(new TreeNode(0));
if (memo.containsKey(n))
return memo.get(n);

List<TreeNode> ans = new ArrayList<>();

for (int leftCount = 0; leftCount < n; ++leftCount) {
final int rightCount = n - 1 - leftCount;
for (TreeNode left : allPossibleFBT(leftCount))
for (TreeNode right : allPossibleFBT(rightCount)) {
ans.get(ans.size() - 1).left = left;
ans.get(ans.size() - 1).right = right;
}
}

memo.put(n, ans);
return ans;
}

private Map<Integer, List<TreeNode>> memo = new HashMap<>();
}
``````

## Python

``````class Solution:
@lru_cache(None)
def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
if n % 2 == 0:
return []
if n == 1:
return [TreeNode(0)]

ans = []

for leftCount in range(n):
rightCount = n - 1 - leftCount
for left in self.allPossibleFBT(leftCount):
for right in self.allPossibleFBT(rightCount):
ans.append(TreeNode(0))
ans[-1].left = left
ans[-1].right = right

return ans
``````