05 August 2008
二叉树的抢劫房子，root是入口
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int rob(TreeNode root) {
int[] num = dfs(root);
return Math.max(num[0], num[1]);
}
private int[] dfs(TreeNode x) {
if (x == null) return new int[2];
int[] left = dfs(x.left);
int[] right = dfs(x.right);
int[] res = new int[2];
res[0] = left[1] + right[1] + x.val;
res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
return Math.max(robInclude(root), robExclude(root));
}
public int robInclude(TreeNode node) {
if(node == null) return 0;
return robExclude(node.left) + robExclude(node.right) + node.val;
}
public int robExclude(TreeNode node) {
if(node == null) return 0;
return rob(node.left) + rob(node.right);
}
}