打家劫舍2所遇到的环形问题,可将“环”转化为“线”问题,会是三种情况:1.不加首尾。2.加尾不加首。3.加首不加尾。打家劫舍3有点复杂,怎么会有这样的小偷啊???偷东西还会看是不是二叉树!!!???
打家劫舍3的代码如下:
public int rob3(TreeNode root) {
int[] res = robAction1(root);
return Math.max(res[0], res[1]);
}
int[] robAction1(TreeNode root) {
int res[] = new int[2];
if (root == null)
return res;
int[] left = robAction1(root.left);
int[] right = robAction1(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
// 不偷:Max(左孩子不偷,左孩子偷) + Max(右孩子不偷,右孩子偷) // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + // Math.max(rob(root.right)[0], rob(root.right)[1]) // 偷:左孩子不偷+ 右孩子不偷 + 当前节点偷 // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;