|
| 1 | +''' |
| 2 | +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. |
| 3 | + |
| 4 | +Determine the maximum amount of money the thief can rob tonight without alerting the police. |
| 5 | + |
| 6 | +Example 1: |
| 7 | + 3 |
| 8 | + / \ |
| 9 | + 2 3 |
| 10 | + \ \ |
| 11 | + 3 1 |
| 12 | +Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. |
| 13 | +Example 2: |
| 14 | + 3 |
| 15 | + / \ |
| 16 | + 4 5 |
| 17 | + / \ \ |
| 18 | + 1 3 1 |
| 19 | +Maximum amount of money the thief can rob = 4 + 5 = 9. |
| 20 | +''' |
| 21 | +# Definition for a binary tree node. |
| 22 | +# class TreeNode(object): |
| 23 | +# def __init__(self, x): |
| 24 | +# self.val = x |
| 25 | +# self.left = None |
| 26 | +# self.right = None |
| 27 | + |
| 28 | +class Solution(object): |
| 29 | + def rob(self, root): |
| 30 | + def gain(root): |
| 31 | + if root == None: |
| 32 | + return 0 |
| 33 | + o1 = root.val |
| 34 | + if o1 < 0: |
| 35 | + return -o1 |
| 36 | + if root.left: |
| 37 | + o1 += gain(root.left.left) + gain(root.left.right) |
| 38 | + if root.right: |
| 39 | + o1 += gain(root.right.left) + gain(root.right.right) |
| 40 | + o2 = gain(root.left) + gain(root.right) |
| 41 | + o = max(o1,o2) |
| 42 | + root.val = -1*o |
| 43 | + return o |
| 44 | + return gain(root) |