Skip to content

337 House Robber III

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.

Idea:

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization

Time complexity: O(n^2) Space complexity: O(n)

// Running time: 1289 ms
class Solution {
public:
  int rob(TreeNode* root) {
    if (root == nullptr) return 0;
    int val = root->val;
    int ll = root->left ? rob(root->left->left) : 0;
    int lr = root->left ? rob(root->left->right) : 0;
    int rl = root->right ? rob(root->right->left) : 0;
    int rr = root->right ? rob(root->right->right) : 0;
    return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));
  }
};

Solution 2: Recursion w/ memorization

Time complexity: O(n) Space complexity: O(n)

// Running time: 15 ms
class Solution {
public:
  int rob(TreeNode* root) {
    if (root == nullptr) return 0;
    if (m_.count(root)) return m_[root];
    int val = root->val;
    int ll = root->left ? rob(root->left->left) : 0;
    int lr = root->left ? rob(root->left->right) : 0;
    int rl = root->right ? rob(root->right->left) : 0;
    int rr = root->right ? rob(root->right->right) : 0;
    return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));
  }
private:
  unordered_map<TreeNode*, int> m_;
};

Solution 3: Recursion return children’s value

// Running time: 10 ms (beats 97.57%)
class Solution {
public:
  int rob(TreeNode* root) {
    int l = 0;
    int r = 0;
    return rob(root, l, r);
  }
private:
  // return rob(root) and stores rob(root->left/right) in l/r.
  int rob(TreeNode* root, int& l, int& r) {
    if (root == nullptr) return 0;
    int ll = 0;
    int lr = 0;
    int rl = 0;
    int rr = 0;
    l = rob(root->left, ll, lr);
    r = rob(root->right, rl, rr);
    return max(root->val + ll + lr + rl + rr, l + r);
  }
};
    1. House Robber