题目描述：
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.
题目大意：
小偷又给自己找了一个新的偷盗场所。这片区域只有一个入口，叫做“根”。除了根以外，每一个房间有且仅有一个父级房间。在踩点之后，聪明的盗贼发现“所有的房间形成了一棵二叉树”。如果两个有边直接相连的房间在同一晚上都失窃，就会自动联络警察。
判断盗贼在不惊动警察的情况下最多可以偷到的金钱数目。
测试用例如题目描述。
解题思路：
解法I 深度优先搜索（DFS）
深度优先遍历二叉树，每次遍历返回两个值：分别表示偷窃或者不偷窃当前节点可以获得的最大收益。
状态转移方程见代码。
参考LeetCode Discuss：https://leetcode.com/discuss/91597/easy-understanding-solution-with-dfs
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;
}
}
解法II 记忆化搜索（DFS + Memoization）
记当前房间为root，如果偷窃当前房间，则其左右孩子left和right均不能偷窃；而其4个孙子节点（ll，lr，rl，rr）不受影响。
因此最大收益为：
maxBenifit = max(rob(left) + rob(right), root.val + rob(ll) + rob(lr) + rob(rl) + rob(rr))
使用字典valMap记录每一个访问过的节点，可以避免重复运算。
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, '')
本文链接：http://bookshadow.com/weblog/2016/03/13/leetcode-house-robber-iii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
