## 题目描述：

LeetCode 337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

```     3
/ \
2   3
\   \
3   1
```

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

```     3
/ \
4   5
/ \   \
1   3   1
```

Maximum amount of money the thief can rob = 4 + 5 = 9.

## Java代码：

``````public 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;
}
}
``````

`maxBenifit = max(rob(left) + rob(right), root.val + rob(ll) + rob(lr) + rob(rl) + rob(rr))`

## Python代码：

``````# 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
"""
valMap = dict()
def solve(root, path):
if root is None: return 0
if path not in valMap:
left, right = root.left, root.right
ll = lr = rl = rr = None
if left:  ll, lr = left.left, left.right
if right: rl, rr = right.left, right.right
passup = solve(left, path + 'l') + solve(right, path + 'r')
grabit = root.val + solve(ll, path + 'll') + solve(lr, path + 'lr') \
+ solve(rl, path + 'rl') + solve(rr, path + 'rr')
valMap[path] = max(passup, grabit)
return valMap[path]
return solve(root, '')
``````

Pingbacks已关闭。