337. 打家劫舍
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)厘熟。這個(gè)地區(qū)只有一個(gè)入口鸵贬，我們稱之為“根”。 除了“根”之外搁胆，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后邮绿，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”渠旁。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警船逮。
計(jì)算在不觸動(dòng)警報(bào)的情況下顾腊，小偷一晚能夠盜取的最高金額。
思路一：遞歸
1挖胃、偷該節(jié)點(diǎn)杂靶，則不偷左右節(jié)點(diǎn)，偷左右節(jié)點(diǎn)的左右節(jié)點(diǎn)酱鸭。
int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)
2吗垮、不偷該節(jié)點(diǎn)，則偷該節(jié)點(diǎn)的左右節(jié)點(diǎn)凹髓。
int method2 = rob(root.left) + rob(root.right);
int result = Math.max(method1, method2);
class Solution {
public:
int rob(TreeNode* root) {
if(!root)
return 0;
int s1=root->val;
if(root->left)
{
s1+=rob(root->left->left)+rob(root->left->right);
}
if(root->right)
{
s1+=rob(root->right->left)+rob(root->right->right);
}
int s2=rob(root->left)+rob(root->right);
return max(s1,s2);
}
};
遞歸的時(shí)間復(fù)雜度O（2^n）烁登，空間復(fù)雜度O（n）。然而蔚舀，遞歸超時(shí)了饵沧，怎么辦呢？
思路二：動(dòng)態(tài)規(guī)劃
可以發(fā)現(xiàn)赌躺，在遞歸時(shí)捷泞，每求一次節(jié)點(diǎn)金額，需要重復(fù)訪問多次左右子樹寿谴，所以可以提前把偷過(guò)的子樹盜取的最大金額保存到一個(gè)哈希表锁右。從底向上保存偷或不偷該節(jié)點(diǎn)能達(dá)到的最大金額。
以上的算法對(duì)二叉樹做了一次后序遍歷讶泰，時(shí)間復(fù)雜度是 O(n)咏瑟；由于遞歸會(huì)使用到棧空間痪署，空間代價(jià)是 O(n)码泞，哈希表的空間代價(jià)也是 O(n)，故空間復(fù)雜度也是 O(n)狼犯。
class Solution {
public:
map<TreeNode*,int> m;
int rob(TreeNode* root) {
if(!root)
return 0;
if(m[root]>0)
return m[root];
int s1=root->val;
if(root->left)
{
s1+=rob(root->left->left)+rob(root->left->right);
}
if(root->right)
{
s1+=rob(root->right->left)+rob(root->right->right);
}
int s2=rob(root->left)+rob(root->right);
m[root]=max(s1,s2);
return m[root];
}
};
思路三：優(yōu)化動(dòng)態(tài)規(guī)劃
上面的方法每次保存的值為最大值余寥，不確定是否偷該節(jié)點(diǎn)领铐，還要訪問孫子節(jié)點(diǎn)。為了簡(jiǎn)化宋舷，我們可以設(shè)計(jì)一個(gè)結(jié)構(gòu)绪撵，表示某個(gè)節(jié)點(diǎn)的f(偷)和 g (不偷)值，在每次遞歸返回的時(shí)候祝蝠，都把這個(gè)點(diǎn)對(duì)應(yīng)的f(偷)和 g (不偷)返回給上一級(jí)調(diào)用音诈，這樣可以省去哈希表的空間。將每個(gè)節(jié)點(diǎn)偷與不偷能達(dá)到的最大金額保存為一個(gè)pair绎狭。同樣细溅，也是分兩種情況：
1、偷該點(diǎn)
那么不能偷其左右節(jié)點(diǎn)儡嘶；
2喇聊、不偷該點(diǎn)
可以偷其左右節(jié)點(diǎn)，也可以不偷其左右節(jié)點(diǎn)蹦狂，按照最大值誓篱。
class Solution {
public:
int rob(TreeNode* root) {
if(!root)
return 0;
return max(dfs(root).first,dfs(root).second);
}
pair<int,int> dfs(TreeNode* root){
pair<int,int> result={0,0};
if(!root)
return result;
pair<int,int> Left=dfs(root->left);
pair<int,int> Right=dfs(root->right);
result.first=max(Left.first,Left.second)+max(Right.first,Right.second);
result.second=root->val+Left.first+Right.first;
return result;
}
};
時(shí)間復(fù)雜度：O(n)。上文中已分析鸥咖。
空間復(fù)雜度：O(n)燕鸽。雖然優(yōu)化過(guò)的版本省去了哈希表的空間兄世，但是椞淅保空間的使用代價(jià)依舊是 O(n），故空間復(fù)雜度不變御滩。
