Share My Python recursive solution using Memo (DP)


  • 0

    f means including root, s means not including root

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.memo = {}
            return self.helper(root)
    
        def helper(self, root):
            if not root:   # if not root
                return 0
    
            if root not in self.memo:  # if it is not in memo
                val = 0
                if root.left:  # we calculate not have left
                    val += self.helper(root.left.left) + self.helper(root.left.right)
                if root.right: # we calculate not have right
                    val += self.helper(root.right.left) + self.helper(root.right.right)
                f = root.val+val    # max include root
                s = self.helper(root.left) + self.helper(root.right) # max not include root
                self.memo[root] = max(f, s)
            return self.memo[root]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.