The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.



Determine the maximum amount of money the thief can rob tonight without alerting the police.


Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.


Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.


Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def superrob(node):
             # returns tuple of size two (now, later)
             # now: max money earned if input node is robbed
             # later: max money earned if input node is not robbed
 
             # base case
             if not node: return (0, 0)
 
             # get values
             left, right = superrob(node.left), superrob(node.right)
 
             # rob now
             now = node.val + left[1] + right[1]
 
             # rob later
             later = max(left) + max(right)
 
             return (now, later)
 
         return max(superrob(root))


# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         yield_value = {}
         
         def helper(node, can_rob):
             if not node:
                 return 0
             
             if (node.left, True) not in yield_value:
                 left_yield_t = helper(node.left, True)
                 yield_value[(node.left, True)] = left_yield_t
             if (node.right, True) not in yield_value:
                 right_yield_t = helper(node.right, True)
                 yield_value[(node.right, True)] = right_yield_t            
             if (node.left, False) not in yield_value:
                 left_yield_f = helper(node.left, False)
                 yield_value[(node.left, False)] = left_yield_f
             if (node.right, False) not in yield_value:
                 right_yield_f = helper(node.right, False)
                 yield_value[(node.right, False)] = right_yield_f
                 
             if not can_rob:
                 return yield_value[(node.left, True)] + yield_value[(node.right, True)]
             
             else:
                 return max(
                     (node.val + yield_value[(node.left, False)] + yield_value[(node.right, False)]), 
                     (yield_value[(node.left, True)] + yield_value[(node.right, True)] )
                 )
         
         return helper(root, True)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         valMap = dict()
         def solve(root, path):
             if root is None: return 0
             if path not in valMap:
                 left, right = root.left, root.right
                 ll = lr = rl = rr = None
                 if left:  ll, lr = left.left, left.right
                 if right: rl, rr = right.left, right.right
                 passup = solve(left, path + 'l') + solve(right, path + 'r')
                 grabit = root.val + solve(ll, path + 'll') + solve(lr, path + 'lr') \
                          + solve(rl, path + 'rl') + solve(rr, path + 'rr')
                 valMap[path] = max(passup, grabit)
             return valMap[path]
         return solve(root, '')
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 
 class Solution(object):
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def superrob(node):
             # returns tuple of size two (now, later)
             # now: max money earned if input node is robbed
             # later: max money earned if input node is not robbed
             
             # base case
             if not node: return (0, 0)
             
             # get values
             left, right = superrob(node.left), superrob(node.right)
             
             # rob now
             now = node.val + left[1] + right[1]
             
             # rob later
             later = max(left) + max(right)
             
             return (now, later)
             
         return max(superrob(root))

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def dfs(root):
             if root == None:
                 return [0, 0]
             
             left = dfs(root.left)
             right = dfs(root.right)
             res = [0, 0]
             res[0] = root.val + left[1] + right[1]
             res[1] = max(left[0], left[1]) + max(right[0], right[1])
             return res
         res = dfs(root)
         print(res)
         return max(res[0], res[1])
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         return self.robSub(root, {})
     
     def robSub(self, root, dictionary):
         if root == None:
             return 0
         if root in dictionary:
             return dictionary[root]
         value = 0
         if root.left != None:
             value += self.robSub(root.left.left, dictionary) + self.robSub(root.left.right, dictionary)
         if root.right != None:
             value += self.robSub(root.right.left, dictionary) + self.robSub(root.right.right, dictionary)
         value = max(value+root.val, self.robSub(root.left,dictionary)+self.robSub(root.right,dictionary))
         dictionary[root] = value
         return value
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         
         dp = {}
         
         def rob1(node):
             if node.left and node.left not in dp:
                 dp[node.left] = rob1(node.left)
             if node.right and node.right not in dp:
                 dp[node.right] = rob1(node.right)
             
             temp = node.val
 
             if node.left and node.left.left:
                 temp += dp[node.left.left]
             if node.left and node.left.right:
                 temp += dp[node.left.right]
             if node.right and node.right.left:
                 temp += dp[node.right.left]
             if node.right and node.right.right:
                 temp += dp[node.right.right]
             
             t = 0
             if node.left:
                 t += dp[node.left]
             if node.right:
                 t += dp[node.right]
             
             return max(t, temp)
         
         return rob1(root)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         self.dict = {}
         return self.recurse(root)
         
     def recurse(self, root):
         if root is None:
             return 0
         if root in self.dict:
             return self.dict[root]
         else:
             x = self.recurse(root.left)
             y = self.recurse(root.right)
             a = 0 if root.left is None else self.recurse(root.left.left)
             b = 0 if root.left is None else self.recurse(root.left.right)
             c = 0 if root.right is None else self.recurse(root.right.left)
             d = 0 if root.right is None else self.recurse(root.right.right)
             ans = max(root.val+a+b+c+d , x+y)
             self.dict[root] = ans
             return ans

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         # if not root:
         #     return 0
         # res = 0
         # if root.left:
         #     if root.left.left:
         #         res += self.rob(root.left.left)
         #     if root.left.right:
         #         res += self.rob(root.left.right)
         # if root.right:
         #     if root.right.left:
         #         res += self.rob(root.right.left)
         #     if root.right.right:
         #         res += self.rob(root.right.right)
         # return max(res + root.val, self.rob(root.left) + self.rob(root.right))
         
         print(self.helper(root))
         return max(self.helper(root))
         
     def helper(self, root):
         if not root:
             return [0,0]
         left = self.helper(root.left)
         right = self.helper(root.right)
         res = [0, 0] # index = 0 not rob, index 1 rob
         res[0] = max(left) + max(right)
         res[1] = left[0] + right[0] + root.val
         return res
         
              
             
             
         

class Solution:
 
     def rob_node(self, node):
         if not node.left:
             rob_node_left, not_rob_node_left = 0, 0
         else:
             rob_node_left, not_rob_node_left = self.rob_node(node.left)
         if not node.right:
             rob_node_right, not_rob_node_right = 0, 0
         else:
             rob_node_right, not_rob_node_right = self.rob_node(node.right)
         return node.val + not_rob_node_left + not_rob_node_right, \
                max(rob_node_left, not_rob_node_left) + max(rob_node_right, not_rob_node_right)
 
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         rob_root, not_rob_root = self.rob_node(root)
         return max(rob_root, not_rob_root)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     
     def rob2(self, root):
         
         if root is None:
             return (0,0)
         
         with_left, without_left = self.rob2(root.left)
             
         with_right, without_right = self.rob2(root.right)
         
         with_root = without_left + without_right + root.val
         
         without_root = max(with_left, without_left) + max(with_right, without_right)
         
         return (with_root, without_root)
     
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         return max(self.rob2(root))
             
         

class Solution:
     def __init__(self):
         self.data_dict = dict()
 
     def rob(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
 
         if not root:
             return 0
 
         if root in self.data_dict:
             return self.data_dict[root]
 
         if not root.left and not root.right:
             self.data_dict[root] = root.val
             return root.val
 
         res = 0
 
         if root.left:
             res += self.rob(root.left.left) + self.rob(root.left.right)
 
         if root.right:
             res += self.rob(root.right.left) + self.rob(root.right.right)
 
         res = max(self.rob(root.left) + self.rob(root.right), res + root.val)
         self.data_dict[root] = res
 
         return res