Very simple bottom-up python with explaination


  • 0
    S
    class Solution(object):
    """
    For each node, we return two states: contains this node and do not contain it
    So, as for the parent node:
        1.contain:         parent's value + not-contain-left-child + not-contain-right-child
        2.do not contain:  max(contain-left-child, not-contain-left-child)+max(contain-right-child, not-contain-right-child)
    """
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def helper(root):
            if not root: return (0, 0)
            hasLeft, notHasLeft = helper(root.left)
            hasRight, notHasRight= helper(root.right)
            return root.val+notHasLeft+notHasRight, max(hasLeft, notHasLeft)+max(hasRight, notHasRight)
        return max(helper(root))

Log in to reply
 

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