Python DFS + memoization


  • 0
    T
    class Solution(object):
        _memo = {}
        
        def rob(self, root, prevRobbed = False):
            """
            :type root: TreeNode
            :rtype: int
            """
            # dfs of possible valuables
            # w/ memo
            
            if not root:
                 return 0
                 
            if prevRobbed:
                return self.rob(root.left, False) + self.rob(root.right, False)
            else:
                if not root in self._memo:
                    self._memo[root] = max(self.rob(root.left, False) + self.rob(root.right, False), root.val + self.rob(root.left, True) + self.rob(root.right, True))
                
                return self._memo[root]
    

    Simple enough solution. DFS with parameter to indicate if we robbed the parent house and memoization of robbed houses to make sure we don't do extra work.

    Any suggestions on how to improve this answer?


  • 0
    G

    Yes, it is a self-explanatory solution. The idea of my solution is similiar, but my implementation is redundant.


Log in to reply
 

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