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.

Have you met this question in a real interview? Example

  3
 / \
2   3
 \   \ 
  3   1

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

    3
   / \
  4   5
 / \   \ 
1   3   1

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

Solution: Using DFS

Note: It doesn't have to be Rob->n->Rob, it could also be like Rob->n->n->Rob.

Let dfs(n) represents the max money a thief can rob, when reaching node n, the thief has two options: rob the house or don't rob the house. Therefore we can find the maximum money

1. If the thief rob the house money = n->val + dfs(n->left->left) + dfs(n->left->right) + dfs(n->right->left) + dfs(n->right->right);

2. If the thief doesn't rob the house money = dfs(n->left) + dfs(n->right);

    int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
        if (!root) return 0;

        // Check if root already exists in the table
        if (m.count(root)) return m[root];

        int val = 0;
        if (root->left) {
            // If left child exists
            val += dfs(root->left->left, m) + dfs(root->left->right, m);
        }

        if (root->right) {
            // If right child exists
            val += dfs(root->right->left, m) + dfs(root->right->right, m);
        }
        val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));

        m[root] = val;
        return val;
    }

    int houseRobber3(TreeNode * root) {
        if (!root) return 0;

        unordered_map<TreeNode*, int> m;
        return dfs(root, m);
    }

Solution: Return the rob and not rob value

We can return a vector of size 2, including a value contains the current node, and the other value doesn't. The first value means the max money the thief can get if he robs the house, the second value means the max money he can get without robing the house.

Then the max money he can get is the max of these two value.

    int houseRobber3(TreeNode* root) {
        vector<int> res = dfs(root);
        return max(res[0], res[1]);
    }
    vector<int> dfs(TreeNode *root) {
        if (!root) return vector<int>(2, 0);
        vector<int> left = dfs(root->left);
        vector<int> right = dfs(root->right);
        vector<int> res(2, 0);
        res[0] = max(left[0], left[1]) + max(right[0], right[1]);
        res[1] = left[0] + right[0] + root->val;
        return res;
    }

Solution: Passing rob and not rob value as params

The idea is the same as solution 2, except that we pass those values as params.

    int rob(TreeNode* root) {
        int l = 0, r = 0;
        return helper(root, l, r);
    }
    int helper(TreeNode* node, int& l, int& r) {
        if (!node) return 0;
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = helper(node->left, ll, lr);
        r = helper(node->right, rl, rr);
        return max(node->val + ll + lr + rl + rr, l + r);
    }