337

337. House Robber III (Medium)

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

 

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 104

Companies:
Amazon, Google, Microsoft

Related Topics:
Dynamic Programming, Tree, Depth-First Search, Binary Tree

Similar Questions:

• House Robber (Medium)
• House Robber II (Medium)

Solution 1. DP

At each node, we have two options, rob or skip.

If we rob it, the best we can get is node->val + skip(node->left) + skip(node->right) where skip(x) means the best outcome we can get if we skip node x.

If we skip it, the best we can get is best(node->left) + best(node->right), where best(x) means the best outcome we can get at node x (best(x) = max(rob(x), skip(x))).

So we can do a postorder traversal and return a pair of rob(x) and skip(x) at each node x.

// OJ: https://leetcode.com/problems/house-robber-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    pair<int, int> dfs(TreeNode* root) { // rob, skip
        if (!root) return { 0, 0 }; 
        auto [lr, ls] = dfs(root->left);
        auto [rr, rs] = dfs(root->right);
        return { root->val + ls + rs, max(lr, ls) + max(rr, rs) };
    }
public:
    int rob(TreeNode* root) {
        auto [r, s] = dfs(root);
        return max(r, s);
    }
};

Solution 2. DP

When doing post-order traversal, return a pair of numbers indicating:

1. the maximum value we can get at the current node, including both rob and skip.
2. the maximum value we can get if we skip the current node.

// OJ: https://leetcode.com/problems/house-robber-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    pair<int, int> dfs(TreeNode* root) {
        if (!root) return {0, 0};
        auto left = dfs(root->left), right = dfs(root->right);
        int prev = left.first + right.first;
        return { max(root->val + left.second + right.second, prev), prev };
    }
public:
    int rob(TreeNode* root) {
        return dfs(root).first;
    }
};