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 {
private Map<Integer, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> allPossibleFBT(int n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
List<TreeNode> ans = new ArrayList<>();
if (n == 1) {
ans.add(new TreeNode(0));
} else if (n % 2 == 1) {
for (int i = 1; i < n; i += 2) {
int j = n - 1 - i;
for (TreeNode left : allPossibleFBT(i)) {
for (TreeNode right : allPossibleFBT(j)) {
TreeNode currRoot = new TreeNode(0);
currRoot.left = left;
currRoot.right = right;
ans.add(currRoot);
}
}
}
}
memo.put(n, ans);
return ans;
}
}
|
需要意识到一个问题就是full binary tree中nodes的个数是奇数个. 这是关键.
如果给我们的值n是个偶数, 那是凑不成full binary tree的.
如果是奇数, 那我们就要想左树有几个, 右树有几个. 比如n == 7. 可以的组合是:
左: 1 右: 5
左: 3 右: 3
左: 5 右: 1
这样就转化为了subproblem了.
我们用memo来存之前求过的答案.
时间复杂度: O(n) 如果n是奇数, 我们有n / 2种情况, 每种情况只会求因此, 因为有memo.
空间复杂度: O(n) 一层一层下去, 左1, 右n, 然后是左1右n - 2, 然后是左1, 右n - 4…
