# Python Solution (DP) with Explanation

• Every tree node has 2 status - being taken or not. `take` is used for indicating the status.

So there are 2 cases:

1. when the root is taken, then its left or right child must NOT be taken
2. 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))``````

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