# 337. House Robber III 打家劫舍 III

@TOC

## # 题目描述

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.
``````

## # 解题方法

``````# 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
"""
def dfs(root):
# from bottom to top
if not root: return [0, 0] # before layer, no robcurr, robcurr
robleft = dfs(root.left)
robright = dfs(root.right)
norobcurr = robleft[1] + robright[1]
robcurr = max(root.val + robleft[0] + robright[0], norobcurr)
return [norobcurr, robcurr]
return dfs(root)[1]
``````

``````# 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
"""
memo = dict()
return self.helper(root, memo)

def helper(self, root, memo):
if not root:
return 0
if root in memo:
return memo[root]
res = 0
notused = self.helper(root.left, memo) + self.helper(root.right, memo)
used = 0
if root.left:
used += self.helper(root.left.left, memo) + self.helper(root.left.right, memo)
if root.right:
used += self.helper(root.right.left, memo) + self.helper(root.right.right, memo)
res = max(notused, used + root.val)
memo[root] = res
return res
``````

``````# 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
"""
self.d = dict()
return self.helper(root, False)

def helper(self, root, parentUsed):
if not root: return 0
if (root, parentUsed) in self.d:
return self.d[(root, parentUsed)]
res = 0
if parentUsed:
res = self.helper(root.left, False) + self.helper(root.right, False)
else:
res = max(root.val + self.helper(root.left, True) + self.helper(root.right, True), self.helper(root.left, False) + self.helper(root.right, False))
self.d[(root, parentUsed)] = res
return res
``````

## # 日期

2018 年 6 月 22 日 —— 这周的糟心事终于完了 2018 年 12 月 25 日 —— 圣诞节快乐 2019 年 3 月 23 日 —— 周末加油鸭