Python solution using a cache


  • 0
    H
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    
    
    class Solution(object):
        def rob_rec(self,root,cache):
            if root==None:
                return 0
            if root in cache:
                return cache[root]
            if [root.left,root.right]==[None,None]:
                return root.val
            anslist=[]
            for node in [root.left,root.right]:
                anslist.append(self.rob_rec(node,cache))
                if node!=None:
                    anslist.append(self.rob_rec(node.left,cache)+self.rob_rec(node.right,cache))
                else:
                    anslist.append(0)
            l,sl,r,sr=anslist
            cache[root]=max(l+r,sl+sr+root.val)
            return cache[root]
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            return self.rob_rec(root,{})

Log in to reply
 

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