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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal

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:
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):
		if not root:
			return 0
		(rob_root, not_rob_root) = self.rob_node(root)
		return max(rob_root, not_rob_root)


class Solution:

	def __init__(self):
		self.data_dict = dict()

	def rob(self, root):
		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