Every tree node has 2 status - being taken or not. `take`

is used for indicating the status.

So there are 2 cases:

- when the root is taken, then its left or right child must NOT be taken
- when the root is not taken, its left or right child can either be taken or not be taken

So, use dynamic programming and save the sub-optimal solution in a dictionary dp[take][root].

```
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
dp = {True: {}, False: {}}
def search(root, take):
if not root: return 0
if not root.left and not root.right and take: return root.val
if root in dp[take]: return dp[take][root]
if take:
dp[take][root] = search(root.left, False) + search(root.right, False) + root.val
else:
dp[take][root] = max(search(root.left, True), search(root.left, False)) \
+ max(search(root.right, True), search(root.right, False))
return dp[take][root]
return max(search(root, True), search(root, False))
```