In this solution, I define the subproblem: each `root`

I pass to the `helper function`

is the `father node`

in this subproblem. and the `flag`

tell the subproblem if the `father node`

that means`root`

is choose or not choose in the previous problem. If root is choosen (which means `flag`

is `true`

) , so I can not choose the `root's child`

(which is `root.left`

and `root.right`

). And then I have to execute the programme in `flag is True`

. In that , I make a choose again. If `root.left`

and `root.right`

are choosen or not, so i can match they each other.Finally, I choose the optimizer value.

```
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
a = self.helper(root, True) + root.val
b = self.helper(root, False)
return max(a, b)
def helper(self, root, flag):
if root is None:
return 0
elif flag is True:
e = self.helper(root.left, False)
f = self.helper(root.right, False)
return e + f
elif flag is False:
a = 0
b = 0
if root.left is not None:
a = self.helper(root.left, True) + root.left.val
if root.right is not None:
b = self.helper(root.right, True) + root.right.val
c = self.helper(root.left, False)
d = self.helper(root.right, False)
op = max(a+b, a+d, b+c, c+d)
return op
```

Unfortunately, this solution is so slowly. Because, I have to calculate the subproblem again and again. So, I use the `dict`

to store the root value I have calculate it's optimizer value before.

```
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
map = {}
a = self.helper(root, True, map) + root.val
b = self.helper(root, False, map)
return max(a, b)
def helper(self, root, flag, map):
if root is None:
return 0
if (map.get(root,None) is not None) and (flag is False):
return map[root]
elif flag is True:
e = self.helper(root.left, False, map)
f = self.helper(root.right, False, map)
return e + f
elif flag is False:
a = 0
b = 0
if root.left is not None:
a = self.helper(root.left, True, map) + root.left.val
if root.right is not None:
b = self.helper(root.right, True, map) + root.right.val
c = self.helper(root.left, False, map)
d = self.helper(root.right, False, map)
op = max(a+b, a+d, b+c, c+d)
map[root] = op
return op
```