Two Python solutions


  • 0

    Since it's a tree problem, the first came into my mind was a recursive solution. And I used memoization to avoid duplicated calculations.

    Recursive

    memo = {None : 0}
    class Solution(object):
        def rob(self, p):
            """
            :type p: TreeNode
            :rtype: int
            """
            if p not in memo:
                tmp = sum(self.rob(x) for node in (p.left, p.right) if node \
                                      for x in (node.left, node.right))
                memo[p] = max(self.rob(p.left) + self.rob(p.right), p.val + tmp)
            return memo[p]
    

    But memo caused extra space right? Then I came up with a dfs solution which uses only constant space. Here YES and NO means the corresponding total value if we robbed current house or not. And the dfs version beats 98.36% over all the submissions,

    DFS

    class Solution(object):
        def rob(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(node):
                if not node: return 0, 0
                YES_l, NO_l = dfs(node.left)
                YES_r, NO_r = dfs(node.right)
                return node.val + NO_l + NO_r, max(YES_l, NO_l) + max(YES_r, NO_r)
            
            return max(dfs(root))
    

Log in to reply
 

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