題目描述
在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口，我們稱之為根。除了根之外，每棟房子有且隻有一個父房子與之相連。一番偵察之後，聰明的小偷意識到這個地方的所有房屋的排列類似于一棵二叉樹。如果兩個直接相連的房子在同一天晚上被打劫，房屋将自動報警。
計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。
示例1
輸入：
[3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
輸出:
7
解釋：
小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7. 複制
示例2
輸入：
[3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
輸出:
9
解釋：
小偷一晚能夠盜取的最高金額 = 4 + 5 = 9. 複制
題解
這次是在一棵樹上偷竊了，做法還是一樣。對于結點
r
來說，我們還是分為偷和不偷兩種情況。
如果偷的話，它的左右兒子就不能偷了，是以最大價值就是左兒子不偷的最大價值，加上右兒子不偷的最大價值，再加上
r
的價值。
而如果不偷的話，最大價值就是左兒子偷或不偷的最大價值，加上右兒子偷或不偷的最大價值。
因為需要用到兒子結點偷和不偷兩個價值，是以需要在
dfs
時傳回兩個值，用來表示偷和不偷兩個最大價值，具體實作時用
pair
來表示。
可能有人會用另一種實作方式，用
dfs0
表示不偷的最大價值，
dfs1
表示偷的最大價值，然後兩個函數互相調用。注意這樣理論上是可行的，但是會産生很多重複計算，最終會逾時。是以這種方法需要記憶化搜尋，比較麻煩，需要用
map<TreeNode*, int>
來儲存每個結點的答案。
代碼
複雜實作方式（c++）
class Solution {
public:
unordered_map<TreeNode*, int> dp0, dp1;
int dfs0(TreeNode* root) {
if (!root) return 0;
if (dp0.find(root) != dp0.end()) return dp0[root];
int res = 0;
res += max(dfs0(root->left), dfs1(root->left));
res += max(dfs0(root->right), dfs1(root->right));
return dp0[root]=res;
}
int dfs1(TreeNode* root) {
if (!root) return 0;
if (dp1.find(root) != dp1.end()) return dp1[root];
int res = root->val;
res += dfs0(root->left);
res += dfs0(root->right);
return dp1[root]=res;
}
int rob(TreeNode* root) {
if (!root) return 0;
dp0.clear();
dp1.clear();
return max(dfs0(root), dfs1(root));
}
}; 複制
精簡實作方式（c++）
class Solution {
public:
typedef pair<int, int> pii;
pii dfs(TreeNode* root) {
if (!root) return {0, 0};
pii l = dfs(root->left);
pii r = dfs(root->right);
int r0 = max(l.first, l.second) + max(r.first, r.second);
int r1 = l.first + r.first + root->val;
return {r0, r1};
}
int rob(TreeNode* root) {
pii res = dfs(root);
return max(res.first, res.second);
}
}; 複制
參考資料
[1]
LeetCode 337. 打家劫舍 III: https://leetcode-cn.com/problems/house-robber-iii/
[2]
【每日算法Day 104】偷電瓶的周某今天放出來了，還不趕緊做這道題防範一下！: https://godweiyang.com/2020/04/18/leetcode-198/
[3]
【每日算法Day 105】打家劫舍第二彈：看好你的電瓶車！: https://godweiyang.com/2020/04/19/leetcode-213/