image.png
需要memo
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
memo = {}
def helper(root, f):
if not root: return 0
if (root,f) in memo: return memo[(root,f)]
l0, l1 = helper(root.left,0), helper(root.left,1)
r0, r1 = helper(root.right,0), helper(root.right,1)
if f:
memo[(root,f)] = root.val+l0+r0
return root.val+l0+r0
else:
memo[(root,f)] = max(l0,l1)+max(r0,r1)
return max(l0,l1)+max(r0,r1)
if not root: return 0
return max(helper(root, 0), helper(root, 1))
