Recursive Python solution DP + memoization - relatively long


  • 0
    G

    '''

    def rob(self, root):
        if not root:
            return 0
        if self.height(root)==1:
            return root.val
        return max(self.maxAmount(root, True), self.maxAmount(root, False))
    
    def memo(func):
        from functools import wraps
        cache = {}
        @wraps(func)
        def wrap(*args):
            if args not in cache:
                cache[args] = func(*args)
            return cache[args]
        return wrap
        
    @memo
    def maxAmount(self, root, useRoot):
        if not root:
            return 0
        if self.height(root)==1:
            if useRoot==True:
                return root.val
            else:
                return 0
        if useRoot==True:
            lnR=self.maxAmount(root.left, False)
            rnR=self.maxAmount(root.right, False)
            return lnR+rnR+root.val
        if useRoot==False:
            lR=self.maxAmount(root.left, True)
            lnR=self.maxAmount(root.left, False)
            rR=self.maxAmount(root.right, True)
            rnR=self.maxAmount(root.right, False)
            return max(lR+rR, lR+rnR, lnR+rR, lnR+rnR)
    
    @memo
    def height(self, root):
        if not root:
            return 0
        else:
            return max(self.height(root.left), self.height(root.right))+1
    

    '''


Log in to reply
 

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