Leetcode 337. House Robber III

Problem Explanation

The problem describes a situation where a thief is trying to rob houses in an area which is formed like a binary tree. There are two rules that the thief needs to observe:

1. He cannot rob two directly linked houses on the same night as that would alert the police.
2. He can only enter the area via one entrance known as the "root" house.

The goal is to find the maximum amount of money the thief can rob in a single night without alerting the police.

To understand how this works, consider the first input example:

1
2
3Input: [3,2,3,null,3,null,1]
4
5         3
6        / \
7       2   3
8        \   \
9         3   1

The thief can rob the root house (3), the second house on the left (3), and the second house on the right (1) without breaking the two rules. Thus, the maximum amount he can rob in a night is 3 + 3 + 1 = 7.

The problem has been modeled as a binary tree to emulate the rule that no two directly linked houses can be robbed on the same night.

Solutions Approach

The solution to this problem is a dynamic programming approach with a depth first search (DFS) traversal of the binary tree. For each node, we compute two values: the maximum amount the thief can rob if he robs that node (robRoot), and the maximum amount the thief can rob if he does not rob that node (notRobRoot).

To find these amounts, for each node we recursively compute the maximum amounts for its left and right child nodes. The maximum amount if he robs that node is the value of the node plus the maximum amounts for not robbing its left and right children (since he cannot rob a node and its child). The maximum amount if he does not rob that node is the maximum of either robbing or not robbing for both its children.

In the end, the maximum amount the thief can rob is the maximum value between robbing and not robbing the root node.

C++ Solution

Here is a C++ solution.

1
2cpp
3struct T {
4  int robRoot;
5  int notRobRoot;
6};
7
8class Solution {
9 public:
10  int rob(TreeNode* root) {
11    const auto& [robRoot, notRobRoot] = robOrNotRob(root);
12    return max(robRoot, notRobRoot);
13  }
14  // Uses DFS and dynamic programming to find the maximum amount the thief can rob
15  private:
16  T robOrNotRob(TreeNode* root) {
17    if (root == nullptr)
18      return {0, 0};
19    const T l = robOrNotRob(root->left);
20    const T r = robOrNotRob(root->right);
21    return {root->val + l.notRobRoot + r.notRobRoot,
22            max(l.robRoot, l.notRobRoot) + max(r.robRoot, r.notRobRoot)};
23  }
24};

Unfortunately, it's not trivial to translate this code into other languages as the use of automatic structure binding (const auto& [robRoot, notRobRoot]) is not supported in languages like Java and Python. But the basic idea remains the same: compute the max values for each node and recursively combine these values.## Python Solution

Python offers contributions to this algorithm in a concise and readable manner, using list to represent the maximum amounts.

Here is the Python solution:

1
2python
3class Solution:
4    
5    def rob(self, root):
6        def helper(node):
7            # returns two values: the max amount without robbing the node, and the max amount with robbing the node.
8            if not node:
9                return (0, 0)
10            
11            left = helper(node.left)
12            right = helper(node.right)
13            
14            # If we rob this node, its left and right children cannot be robbed. Hence, we choose the larger ones from the children's returned results.
15            rob = node.val + left[1] + right[1]
16            # If we do not rob this node, we are free to choose from robbing or not robbing its children.
17            notRob = max(left) + max(right)
18            
19            return [notRob, rob]
20        
21        return max(helper(root))

JavaScript Solution

The same logic can also be implemented in JavaScript. Here, the two return values (the maximum amount without robbing the node, and the maximum amount with robbing the node) are returned as an array.

Here is the JavaScript solution:

1
2javascript
3var rob = function(root) {
4  function helper(node) {
5    if (node === null) {
6      return [0, 0];
7    }
8
9    let left = helper(node.left);
10    let right = helper(node.right);
11
12    let rob = node.val + left[1] + right[1];
13    let notRob = Math.max(...left) + Math.max(...right);
14
15    return [notRob, rob];
16  }
17
18  return Math.max(...helper(root));
19}

Java Solution

With Java, it's also feasible by creating a class that holds the maximum values.

Here is the Java solution:

1
2java
3class Solution {
4  private class Pair{
5    int rob;
6    int notRob;
7  }
8    
9  public int rob(TreeNode root) {
10    Pair result = helper(root);
11    return Math.max(result.rob, result.notRob);
12  }
13    
14  private Pair helper(TreeNode root) {
15    if (root == null) {
16      Pair pair = new Pair();
17      pair.rob = 0;
18      pair.notRob = 0;
19      return pair;
20    }
21        
22    Pair left = helper(root.left);
23    Pair right = helper(root.right);
24        
25    Pair curr = new Pair();
26      
27    curr.rob = root.val + left.notRob + right.notRob;
28    curr.notRob = Math.max(left.rob, left.notRob) + Math.max(right.rob, right.notRob);
29        
30    return curr;
31  }
32}

Each of these solutions exhibit the same logic: store the max amounts for rob and not rob for each node, and then recursively combine them to calculate the global maximum amounts.