# Two Python solutions

• 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))
``````

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