BiruLyu
6/3/2017 - 6:23 PM

## 337. House Robber III(#1).java

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = self.helper(root)
return max(res[0], res[1])

def helper(self, root) :
if not root :
return 0, 0
left = self.helper(root.left)
right = self.helper(root.right)
return left[1] + right[1] + root.val, max(left[0], left[1]) + max(right[0], right[1])

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
/*rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at root*/
/*
Redefine rob(root) as a new function which will return an array of two elements,
1. the first element of which denotes the maximum amount of money that can be robbed if root is not robbed,
2. while the second element signifies the maximum amount of money robbed if it is robbed.
*/
public class Solution {
public int rob(TreeNode root) {

if(root == null) return 0;

int[] res = robSub(root);

return Math.max(res[0], res[1]);
}

private int[] robSub(TreeNode root) {
if(root == null) return new int[2];

int[] left = robSub(root.left);
int[] right = robSub(root.right);
int[] res = new int[2];

res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];

return res;

}
}

/*
[3,2,3,null,3,null,1]
[3,4,5,1,3,null,1]
[4,1,null,2,null,3]
[1,2,3]
[1]
[2,1,3,null,4]
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
/*rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at root*/
/*
From the point of view of the tree root, there are only two scenarios at the end: root is robbed or is not.
1. If it is, due to the constraint that "we cannot rob any two directly-linked houses", the next level of subtrees that are available would be the four "grandchild-subtrees" (root.left.left, root.left.right, root.right.left, root.right.right).
2.However if root is not robbed, the next level of available subtrees would just be the two "child-subtrees" (root.left, root.right).
We only need to choose the scenario which yields the larger amount of money.
*/
public class Solution {
public int rob(TreeNode root) {

if(root == null) return 0;

int val = 0;

if(root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}

if(root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}

return Math.max(val + root.val, rob(root.left) + rob(root.right));
}

}

/*
[3,2,3,null,3,null,1]
[3,4,5,1,3,null,1]
[4,1,null,2,null,3]
[1,2,3]
[1]
[2,1,3,null,4]
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}

public int[] helper(TreeNode root) {
if (root == null) return new int[2];
int[] left = helper(root.left);
int[] right = helper(root.right);
int include = root.val + left[1] + right[1];
int exclude = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[] {include, exclude};
}
}