class Solution {
private Map<Integer, List<TreeNode>> memo;
public List<TreeNode> allPossibleFBT(int N) {
this.memo = new HashMap<>();
return backtrack(N);
}
private List<TreeNode> backtrack(int n) {
List<TreeNode> ret = new ArrayList<>();
if (n < 1) {
return ret;
}
if (n == 1) {
ret.add(new TreeNode(0));
return ret;
}
if (memo.containsKey(n)) {
return memo.get(n);
}
for (int i = 1; i < n; i++) {
for (TreeNode left : backtrack(i)) {
for (TreeNode right : backtrack(n - i - 1)) {
TreeNode node = new TreeNode(0);
node.left = left;
node.right = right;
ret.add(node);
}
}
}
memo.put(n, ret);
return ret;
}
}