337. House Robber III

需要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))