Leetcode 337. House Robber III (Python)

Related Topic

Depth-First-Search. Tree. Dynamic-Programming.

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.

Sample I/O

Example 1

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

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

Example 2

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

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

Methodology

This question can be solved by Depth First Search + Dynamic Programming

The maxmium amount of money path is either start from the root or not start from the root. If we start from the root then we need to recusivly find totol amount of root.left.left, root.left.right, root.right.left, root.right.right plus root itself. If we do not start from the root then we need to start from root.left and root.right as left root and right root and recursively find totol amount of left root’s and right root’s root.left.left, root.left.right, root.right.left, root.right.right plus root itself. Then we compare start from root and start from left root + right root.

We use dynamic programming because, for each root we will record it’s max amount of the money. This will save a lot of time and space.

Code(DFS+DP)

def rob(self, root: TreeNode) -> int:
        lookup = {}
        def dfs(root):
            if not root: return 0
            if root in lookup: return lookup[root]
            val = 0
            if root.left:
                val+=dfs(root.left.left) + dfs(root.left.right)
            if root.right:
                val+=dfs(root.right.left) + dfs(root.right.right)
            val=max(val+root.val, dfs(root.left)+dfs(root.right))
            lookup[root]=val
            return val
        return dfs(root)

BigO

We traversal all nodes of the tree once so time complexity is O(n)