337.House Robber III

Tags: [tree], [binary_tree], [recursion], [dp], [trick]

Link: https://leetcode.com/problems/house-robber-iii/\#/description

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.

Solution: recursion, trick

# 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):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        money_from_not_rob_root, money_from_rob_root = self.rob_helper(root)
        return max(money_from_not_rob_root, money_from_rob_root)

    def rob_helper(self, root):
        # base case
        if not root:
            return (0, 0)

        left_sub_money_from_not_rob_root, left_sub_money_from_rob_root = self.rob_helper(root.left)
        right_sub_money_from_not_rob_root, right_sub_money_from_rob_root = self.rob_helper(root.right)

        money_from_not_rob_root = max(left_sub_money_from_not_rob_root, left_sub_money_from_rob_root) +\
                                  max(right_sub_money_from_not_rob_root, right_sub_money_from_rob_root)

        money_from_rob_root = root.val + left_sub_money_from_not_rob_root + right_sub_money_from_not_rob_root

        return (money_from_not_rob_root, money_from_rob_root)

Revelation:

• If the thief robs the root, he cannot rob root.left and root.right.
• If the thief doesn't rob the root, he can rob any node in the root's left subtree and root's right subtree.
• More explanation about why the above idea comes out can see this reference: https://leetcode.com/problems/house-robber-iii/\#/solutions

Note:

• Time complexity = O(n), n is the number of nodes of this tree. Each node we just visited once.

Time Limited Exceeded

# 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):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        memo = {}
        return self.rob_helper(root, memo)

    def rob_helper(self, root, memo):
        if not root:
            return 0

        if root in memo:
            return memo[root]

        # not rob root
        money_if_not_rob_root = self.rob(root.left) + self.rob(root.right)

        # rob root
        money_if_rob_root = root.val
        if root.left:
            money_if_rob_root += self.rob(root.left.left) + self.rob(root.left.right)

        if root.right:
            money_if_rob_root += self.rob(root.right.left) + self.rob(root.right.right)

        max_money = max(money_if_not_rob_root, money_if_rob_root)
        memo[root] = max_money
        return max_money

Note:

• In Python, the custom object can be used as the key of map and set, because the default __hash_ function will return id(x) / 16, id() is a Python build_in function which will return the object's id. For example, there is a custom class called Hello, we can initialize an object, hello = Hello(), id(hello) will return the id of object "hello".
• Time complexity = O(n), n is the number of nodes of the given tree. Personally I think the reason this algorithm is slower than the first solution above is because there are many extra calls self.rob_helper(...) in this algorithm. Even though if the current root has been put into the memo, the self.rob_helper(...) can immediately return the memo[root], but it still wast some time during calling the self.rob_helper(...).

Time Limited Exceeded

# 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):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # base case
        if not root:
            return 0

        # not rob root
        money_if_not_rob_root = self.rob(root.left) + self.rob(root.right)

        # rob root
        money_if_rob_root = root.val
        if root.left:
            money_if_rob_root += self.rob(root.left.left) + self.rob(root.left.right)

        if root.right:
            money_if_rob_root += self.rob(root.right.left) + self.rob(root.right.right)

        return max(money_if_not_rob_root, money_if_rob_root)