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:

1
2
3
4
5

 3
/ \
   2   3
\   \ 
 3   1

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

Example 2:

1
2
3
4
5

 3
/ \
   4   5
  / \   \ 
 1   3   1

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

Solution

• DFS: 返回值为抢劫节点node,和不抢劫node的收益
• 抢劫: 则不能抢劫子节点，return no_rob_L + no_rob_R + node.val
• 不抢劫: 则无法确定是否抢劫左右节点 return max(no_rob_R, rob_R)+max(no_rob_L, rob_L)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    # DFS
    # return: 抢劫node的收益， 不抢劫node的受益
    def dfs(self,node):
        if node == None:
            return 0,0
        rob_L, no_rob_L = self.dfs(node.left)
        rob_R, no_rob_R = self.dfs(node.right)
        return no_rob_L+no_rob_R+node.val, max(no_rob_R,rob_R) + max(no_rob_L, rob_L)


    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        ret = self.dfs(root)
        return max(ret[0],ret[1])