一. 題目描述
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:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
二. 題目分析
該題是House Robber II和House Robber的後續。
題目的意思是，小偷找到了一個新的偷盜場所。這片區域只有一個入口，叫做“根”。除了根以外，每個屋子有且僅有一個父屋子。在踩點之後盜賊發現，所有的房間構造形成了一棵二叉樹。如果兩個直接相連的屋子在同時被盜竊，就會驚動警察。
編寫函數判斷盜賊在不驚動警察的情況下最多可以偷到的金錢數目。測試用例如題目描述。
針對該題，可使用深度優先搜索來解決。對於當前節點，只有盜竊和不盜竊兩種操作，這取決於當前節點的子節點的狀態，可用兩個變量表示：pre和curr：
pre：當前節點（屋子）不偷盜時，所能獲得的收益；取決於在該節點的兩個子節點被偷盜時的收益之和。
curr：當前節點（屋子）偷盜時，所能獲得的收益；由於相鄰節點不能同時偷盜否則會引來警察，所以兩個子節點不能偷盜，此時收益等於：父節點->val + 左子節點->pre + 右子節點->pre。
比較兩種收益pre和curr，取較大者作為當前節點的最大收益。
三. 示例代碼
/**
* 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:
struct Money {
int pre; // 該節點不偷，收益為子節點偷的情況下的收益和
int curr; // 該節點處偷，加上兩子節點不偷時的收益
Money():pre(0), curr(0){}
};
int rob(TreeNode* root) {
Money sum = dfs(root);
return sum.curr;
}
Money dfs(TreeNode* root)
{
if (root == NULL) return Money();
Money leftMoney = dfs(root->left); // 當前節點的左子節點收益情況
Money rightMoney = dfs(root->right); // 當前節點的右子節點收益情況
Money sumMoney;
sumMoney.pre = leftMoney.curr + rightMoney.curr; // 當前節點不偷
sumMoney.curr = max(sumMoney.pre, root->val + leftMoney.pre + rightMoney.pre);
return sumMoney;
}
};
四. 小結
該題屬於DFS的經典題目。
