# House Robber III    ## 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 + r + node.val
return with_max, without_max

``````