LeetCode 337. House Robber IIIΒΆ

Solution 0:

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """


        # my problem here is it breaks the recursion property and it won't cover all cases
        def dfs(root, robbed):
            if not root:
                return
            if level % 2 == 0:
                self.even += root.val
            else:
                self.odd += root.val

            dfs(root.left, level+1)
            dfs(root.right, level+1)
        value1 = dfs(root, True)

        return max(self.even, self.odd)

Solution 1:

class Solution(object):
    def rob(self, root):
        # my problem here is it breaks the recursion property and it won't cover all cases
        # instead of checking level, we need to check ROBBED or NOT of its parent

        # the standard solution is to deal with ROBBED or NOT at the same time with a [0, 1]
        def dfs(root):
            if not root:
                return [0, 0]
            left = dfs(root.left)
            right = dfs(root.right)
            rob_curr = left[1]+right[1] + root.val
            notrob_curr = max(left[0], left[1])+max(right[0], right[1])
            return [rob_curr, notrob_curr]

        res = dfs(root)
        return max(res)