Python Solution (DP) with Explanation

  • 0

    Every tree node has 2 status - being taken or not. take is used for indicating the status.

    So there are 2 cases:

    1. when the root is taken, then its left or right child must NOT be taken
    2. when the root is not taken, its left or right child can either be taken or not be taken

    So, use dynamic programming and save the sub-optimal solution in a dictionary dp[take][root].

    class Solution(object):
        def rob(self, root):
            :type root: TreeNode
            :rtype: int
            dp = {True: {}, False: {}}
            def search(root, take):
                if not root: return 0
                if not root.left and not root.right and take: return root.val
                if root in dp[take]: return dp[take][root]
                if take:
                    dp[take][root] = search(root.left, False) + search(root.right, False) + root.val
                    dp[take][root] = max(search(root.left, True), search(root.left, False)) \
                                     + max(search(root.right, True), search(root.right, False))
                return dp[take][root]
            return max(search(root, True), search(root, False))

Log in to reply

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