题目
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.
解题思路
DP,f(n)表示抢该节点的最优值，g(n)表示不抢这个点的最优值，max(f(root), g(root))为所求
f[root] = root.val + g[root.left] + g[root.right]
g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])
代码
class Solution:
def rob(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
f[root] = root.val + g[root.left] + g[root.right]
g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])
f, g = defaultdict(int), defaultdict(int)
dfs(root)
return max(f[root], g[root])
class Solution:
def rob(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return (0, 0)
left = dfs(root.left)
right = dfs(root.right)
f = root.val + left[1] + right[1]
g = max(left) + max(right)
return (f, g)
return max(dfs(root))
