Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public List<TreeNode> allPossibleFBT(int n) {
Map<Integer, List<TreeNode>> cache = new HashMap<>();
return allPossibleFBT(n, cache);
}
private List<TreeNode> allPossibleFBT(int n, Map<Integer, List<TreeNode>> cache) {
List<TreeNode> resultList = new ArrayList<>();
if ((n & 1) == 0) {
cache.put(n, resultList);
return resultList;
}
if (n == 1) {
resultList.add(new TreeNode());
cache.put(n, resultList);
return resultList;
}
for (int leftNodes = 1; leftNodes <= n - 2; leftNodes += 2) {
int rightNodes = n - 1 - leftNodes;
List<TreeNode> leftRoots = allPossibleFBT(leftNodes);
List<TreeNode> rightRoots = allPossibleFBT(rightNodes);
for (TreeNode leftRoot : leftRoots) {
for (TreeNode rightRoot : rightRoots) {
TreeNode root = new TreeNode();
root.left = leftRoot;
root.right = rightRoot;
resultList.add(root);
}
}
}
cache.put(n, resultList);
return resultList;
}
}
|
自顶向下递归。
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public List<TreeNode> allPossibleFBT(int n) {
List<List<TreeNode>> dpList = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
dpList.add(new ArrayList<>());
}
dpList.get(1).add(new TreeNode());
for (int i = 3; i <= n; i += 2) {
List<TreeNode> nodeList = dpList.get(i);
for (int leftNodes = 1; leftNodes < i - 1; leftNodes += 2) {
int rightNodes = i - 1 - leftNodes;
for (TreeNode leftRoot : dpList.get(leftNodes)) {
for (TreeNode rightRoot : dpList.get(rightNodes)) {
TreeNode root = new TreeNode();
root.left = leftRoot;
root.right = rightRoot;
nodeList.add(root);
}
}
}
}
return dpList.get(n);
}
}
|
自底向上递推。
References
894. All Possible Full Binary Trees