Python O(n) code: Optimized for Readability


  • 6
    W

    Implementing the decoupled recursive approach detailed here

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def superrob(node):
                # returns tuple of size two (now, later)
                # now: max money earned if input node is robbed
                # later: max money earned if input node is not robbed
                
                # base case
                if not node: return (0, 0)
                
                # get values
                left, right = superrob(node.left), superrob(node.right)
                
                # rob now
                now = node.val + left[1] + right[1]
                
                # rob later
                later = max(left) + max(right)
                
                return (now, later)
                
            return max(superrob(root))
    

Log in to reply
 

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