题目描述
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.
Example1:
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.
解题思路
- 参考 博客
- 这种问题是很典型的递归问题，可以利用回溯法来做，
- 因为当前的计算需要依赖之前的结果，那么对于某一个节点，如果其左子节点存在，通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，
- 那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可，
- 但是这种方法无法通过 OJ，超时了，所以必须优化这种方法，这种方法重复计算了很多地方，比如要完成一个节点的计算，就得一直找左右子节点计算，可以把已经算过的节点用 HashMap 保存起来，以后递归调用的时候，现在 HashMap 里找，如果存在直接返回，如果不存在，等计算出来后，保存到 HashMap 中再返回，这样方便以后再调用
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
int res = 0;
unordered_map<TreeNode*, int> mmap;
return dfs(root, mmap);
}
int dfs(TreeNode* root, unordered_map<TreeNode*, int>& mmap){
if(root == NULL){
return 0;
}
if(mmap.count(root) != 0){ // 如果之前已经存过值了
return mmap[root];
}
int res = 0;
if(root -> left){ // 对于当前节点，中间隔一个节点root -> left,root -> right,防止出现 NULL -> left的情况
res += dfs(root -> left -> left, mmap) + dfs(root -> left -> right, mmap);
}
if(root -> right){
res += dfs(root -> right -> left, mmap) + dfs(root -> right -> right, mmap);
}
// 最后的结果应该是（算上本次的节点） 上面隔的节点的 + 根节点， 和（不算本次的节点）
res = max(res + root -> val, dfs(root -> left, mmap) + dfs(root -> right, mmap));
mmap[root] = res;
return res;
}
};
如果不打表的话，会报TLE超时
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// unordered_map<TreeNode*, int> mmap;
int rob(TreeNode* root) {
return fun_helper(root);
}
int fun_helper(TreeNode* root){
if(root == nullptr){
return 0;
}
// if(mmap.count(root) != 0){
// return mmap[root];
// }
int res = 0;
if(root -> left){
res += fun_helper(root -> left -> left) + fun_helper(root -> left -> right);
}
if(root -> right){
res += fun_helper(root -> right -> right) + fun_helper(root -> right -> left);
}
res = max(res + root -> val, fun_helper(root -> left) + fun_helper(root -> right));
// mmap[root] = res;
return res;
}
};
