# 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 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

```Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
```

Example 2:

```Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
```

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• 0 <= Node.val <= 10^4

## 解法¶

• 对于每个 root 节点，只有两个可能：组合中包括 root 节点、组合中不包括 root 节点
• 如果包括 root 节点，那么： * 最大和就等于 root.val + 左子数的子树的最大和 + 右子树的子树的最大和 * 因为限制了节点不能相邻，所以上面是左子数的子树和右子树的子树而不是左子数和右子树
• 如果不包括 root 节点，那么： * 最大和就等于左子数的最大和 + 右子树的最大和
• 比较两个可能得出的最大和，取更大的值作为答案

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def rob(self, root):
self._max_sum = 0
self._tmp_store = {}

return self._helper(root)

def _helper(self, root):
if root is None:
return 0

if root in self._tmp_store:
return self._tmp_store[root]

# 包括 root
include_root_left = 0
include_root_right = 0
if root.left is not None:
include_root_left = self._helper(root.left.left) + \
self._helper(root.left.right)
if root.right is not None:
include_root_right = self._helper(root.right.left) + \
self._helper(root.right.right)
include_root_sum = root.val + include_root_left + include_root_right

# 不包括 root
skip_root_left = self._helper(root.left)
skip_root_right = self._helper(root.right)
skip_root_sum = skip_root_left + skip_root_right

_sum = max(include_root_sum, skip_root_sum)
self._tmp_store[root] = _sum

return _sum
```