# My python solution, select or don't select

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

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