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