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:
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.
Related Topics:
Dynamic Programming, Tree, Depth-first Search
Similar Questions:
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) {
if (!root) return {0, 0};
auto a = dfs(root->left), b = dfs(root->right);
return { root->val + a.second + b.second, max(a.first, a.second) + max(b.first, b.second) };
}
public:
int rob(TreeNode* root) {
auto p = dfs(root);
return max(p.first, p.second);
}
};When doing post-order traversal, return a pair of numbers indicating:
- the maximum value we can get at the current node, including both rob and skip.
- 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;
}
};