My python solution, select or don't select


  • 0
    B

    In this solution, I define the subproblem: each root I pass to the helper function is the father node in this subproblem. and the flag tell the subproblem if the father node that meansroot is choose or not choose in the previous problem. If root is choosen (which means flag is true) , so I can not choose the root's child (which is root.left and root.right). And then I have to execute the programme in flag is True. In that , I make a choose again. If root.left and root.right are choosen or not, so i can match they each other.Finally, I choose the optimizer value.

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return 0
            a = self.helper(root, True) + root.val
            b = self.helper(root, False)
            
            return max(a, b)
            
        def helper(self, root, flag):
            if root is None:
                return 0
                
            elif flag is True:
                e = self.helper(root.left, False)
                f = self.helper(root.right, False)
                return e + f
            elif flag is False:
                a = 0
                b = 0
                if root.left is not None:
                    a = self.helper(root.left, True) + root.left.val
                    
                if root.right is not None:
                    b = self.helper(root.right, True) + root.right.val
                    
                c = self.helper(root.left, False)
                d = self.helper(root.right, False)
                
                op =  max(a+b, a+d, b+c, c+d)
                       
                return op
    

    Unfortunately, this solution is so slowly. Because, I have to calculate the subproblem again and again. So, I use the dict to store the root value I have calculate it's optimizer value before.

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return 0
            map = {}
            a = self.helper(root, True, map) + root.val
            b = self.helper(root, False, map)
            
            return max(a, b)
            
        def helper(self, root, flag, map):
            if root is None:
                return 0
                
            if (map.get(root,None) is not None) and (flag is False): 
                return map[root]
            elif flag is True:
                e = self.helper(root.left, False, map)
                f = self.helper(root.right, False, map)
                return e + f
            elif flag is False:
                a = 0
                b = 0
                if root.left is not None:
                    a = self.helper(root.left, True, map) + root.left.val
                    
                if root.right is not None:
                    b = self.helper(root.right, True, map) + root.right.val
                    
                c = self.helper(root.left, False, map)
                d = self.helper(root.right, False, map)
                
                op =  max(a+b, a+d, b+c, c+d)
                
                map[root] = op
                
                return op
    

Log in to reply
 

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