-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathallFullBT.java
More file actions
28 lines (27 loc) · 972 Bytes
/
allFullBT.java
File metadata and controls
28 lines (27 loc) · 972 Bytes
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
import java.util.*;
public class allFullBT {
// recursion + memorization
Map<Integer, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> allPossibleFBT(int N) {
if (!memo.containsKey(N)) {
List<TreeNode> ans = new LinkedList();
if (N == 1) {
ans.add(new TreeNode(0));
} else if (N % 2 == 1) {
for (int x = 0; x < N; ++x) {
int y = N - 1 - x;
for (TreeNode left: allPossibleFBT(x))
for (TreeNode right: allPossibleFBT(y)) {
// 注意这里建新的tree
TreeNode bns = new TreeNode(0);
bns.left = left;
bns.right = right;
ans.add(bns);
}
}
}
memo.put(N, ans);
}
return memo.get(N);
}
}