在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
1
2
3
4
5
6
7
8
9
10
| 输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
|
示例 2:
1
2
3
4
5
6
7
8
9
10
| 输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
|
很显然，对于每个房子，我们有偷和不偷两种状态，我们取的是这两种状态偷盗的金额的最大值。
我们用 f(o)表示选择结点 o 的情况下，o 结点的子树上被选择的结点的最大权值和；g(o)表示不选择结点 o 的情况下，o 结点的子树上被选择的结点的最大权值和；l 和 r 代表 o 的左右孩子。
- 当 o 被选中时，l 和 r 都不能选中，
f(o) = f(l) + f(r);
- 当 o 不被选中时，l 和 r 都能被选中或不被选择，
g(o) = max(f(l), g(l)) + max(f(r), g(r));
第二种情况：二叉树[4,1,null,2,null,3] 的偷盗最大金额为 7 ，选中 4 之后，不能选择子节点 1 ， 对于子节点 1 ，可以有选择 2 和 不选择 2 两种选择，选择 2 得到最后金额 6 ，不选择 2 得到最大金额 7 。即对于一个未选择的根节点，继续不选择子节点有可能会有更好的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
Map<TreeNode, Integer> f = new HashMap<>();
Map<TreeNode, Integer> g = new HashMap<>();
public int rob(TreeNode root) {
dfs(root);
return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
}
public void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
dfs(root.right);
f.put(root, root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) +
Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)) );
}
}
|
时间复杂度O(n)，对二叉树做了一次后序遍历。
空间复杂度O(n)，栈空间O(n)，哈希表O(n)。
我们还可以对空间复杂度进行优化，可以看出，对于 f(o)或g(o)，它们的取值只与f(l)、f(r)、g(l)、g(r)有关，我们在递归返回时返回一个数组，这样就可以不适用哈希表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int rob(TreeNode root) {
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0], rootStatus[1]);
}
public int[] dfs(TreeNode root){
if(root == null){
return new int[]{0, 0};
}
int[] l = dfs(root.left);
int[] r = dfs(root.right);
int selected = root.val + l[1] + r[1];
int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{selected, notSelected};
}
}
|
时间复杂度O(n)，对二叉树做了一次后序遍历。
空间复杂度O(n)，栈空间O(n)。