Easy understand Python solution, using cache


  • 0
    H
    class Solution(object):
        def __init__(self):
            self.cache = {}
        
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root == None:
                return 0
                   
            if root in self.cache:
                return self.cache[root]
            else:
                self.cache[root] = 0
            # if i rob this house, i must start at depth + 2
            rob_root = root.val
            rob_root += self.rob(root.left.left) + self.rob(root.left.right) if root.left != None else 0
            rob_root += self.rob(root.right.left) + self.rob(root.right.right) if root.right != None else 0
            # if I dont rob this house, i start at next depth
            
            rob_next = self.rob(root.left)
            rob_next += self.rob(root.right)
            
            self.cache[root] = max(self.cache[root],max(rob_root,rob_next))
            
            return self.cache[root]
    

  • 0
    H

    Yes, this should be an application of Dynamic Programming


Log in to reply
 

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