Python solution with memorization, easy to understand for beginners //


  • 0

    def findmax(self, root, ss, memory):

        if not root:
            return 0
        
        if (root,ss) in memory:
            return memory[(root,ss)]
            
        mx = root.val if ss else 0
        l = self.findmax(root.left, 0, memory) 
        r = self.findmax(root.right, 0, memory)
        ll = self.findmax(root.left, 1, memory)
        rr = self.findmax(root.right, 1, memory)
        
        if ss:
            mx += l + r
        else:
            mx += max(l+r, l+rr, ll+r, ll+rr)
        
        memory[(root,ss)] = mx
        return mx
        
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        memory = {}
        return max(self.findmax(root, 0, memory), self.findmax(root, 1, memory))

Log in to reply
 

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