House Robber III

Problem Id: 337 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

This problem could be solved by DFS and Dynamic Programming. For each node, it has 2 state with_max and without_max. with_max represents the maximum amount of the sub-tree where the node is the root node, and the node itself is used. without_max represents the max amount of the sub-tree where the node is the root node and the node itself has not been used. So the DP formular is with_max[node] = without_max[node.left] + without_max[node.right] + node.val, without_max[node] = max(with_max[node.left], without_max[node.left]) + max(with_max[node.right], without_max[node.right]). And this problem could be solved by this formular and DFS.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        return max(self._helper(root))

    def _helper(self, node):
        if node is None:
            return 0, 0
        without_max = 0
        l = self._helper(node.left)
        r = self._helper(node.right)
        without_max = max(l) + max(r)
        with_max = l[1] + r[1] + node.val
        return with_max, without_max