原題鏈接：. - 力扣（LeetCode）
小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為?root?。
除了?root?之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果?兩個(gè)直接相連的房子在同一天晚上被打劫?，房屋將自動(dòng)報(bào)警。
給定二叉樹的?root?。返回?在不觸動(dòng)警報(bào)的情況下?，小偷能夠盜取的最高金額?。
示例 1:
輸入: root = [3,2,3,null,3,null,1] 輸出: 7 解釋:?小偷一晚能夠盜取的最高金額 3 + 3 + 1 = 7
示例 2:
輸入: root = [3,4,5,1,3,null,1] 輸出: 9 解釋:?小偷一晚能夠盜取的最高金額 4 + 5 = 9
提示：
- 樹的節(jié)點(diǎn)數(shù)在?
[1, ]?范圍內(nèi) 0 <= Node.val <=
思路：
本題是一道 樹形 DP 類的題目。需要熟悉二叉樹的遍歷和動(dòng)態(tài)規(guī)劃的知識(shí)。由于每個(gè)節(jié)點(diǎn)都需要根據(jù)其子節(jié)點(diǎn)來判斷當(dāng)前狀態(tài)（偷或者不偷），因此本題采用后序遍歷。動(dòng)態(tài)規(guī)劃的 dp 數(shù)組可以僅是一個(gè) int [ ] 數(shù)組，為每一個(gè)節(jié)點(diǎn)創(chuàng)建一個(gè)這樣的 dp 數(shù)組（通過遞歸創(chuàng)建）。數(shù)組里面只有兩個(gè)值，dp [ 0 ] 表示偷當(dāng)前節(jié)點(diǎn)所能獲得的最高金額，dp [ 1 ] 表示不偷當(dāng)前節(jié)點(diǎn)所能獲得的最高金額。 下面是遞歸函數(shù)的寫法：
- 確定函數(shù)的返回值和參數(shù)：返回值是 動(dòng)態(tài)規(guī)劃的數(shù)組 res，參數(shù)是當(dāng)前節(jié)點(diǎn)。
- 終止條件：當(dāng)遇到葉子節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，返回一個(gè) 默認(rèn)值為 0 的 res 數(shù)組，表示當(dāng)前節(jié)點(diǎn)無論偷還是不偷所能獲取的最高金額都是 0 。
- 單層處理邏輯：首先獲取左子節(jié)點(diǎn)的狀態(tài)數(shù)組 leftVal（偷或者不偷所能帶來的最高金額），再獲取右子節(jié)點(diǎn)的狀態(tài)數(shù)組 rightVal 。最后根據(jù)左右子節(jié)點(diǎn)的狀態(tài)來決定當(dāng)前節(jié)點(diǎn)的狀態(tài)數(shù)組 res。res[ 0 ] 表示偷當(dāng)前節(jié)點(diǎn)所能帶來的最高金額，當(dāng)偷當(dāng)前節(jié)點(diǎn)時(shí)，那么這時(shí)不能偷左右子節(jié)點(diǎn)，因此偷當(dāng)前節(jié)點(diǎn)所能帶來的最高金額為 res[ 0 ] = root.val + leftVal [ 1 ]?+ rightVal [ 1 ]。res[ 1 ] 表示不偷當(dāng)前節(jié)點(diǎn)所能帶來的最高金額，當(dāng)不偷當(dāng)前節(jié)點(diǎn)時(shí)，那么這時(shí)是否偷左右子節(jié)點(diǎn)，就是由左右子節(jié)點(diǎn)的狀態(tài)決定的了。res[ 1 ] 為左子節(jié)點(diǎn)的最大金額加上右子節(jié)點(diǎn)的最大金額。res[1]=Math.max(leftVal[0],leftVal[1])+Math.max(rightVal[0],rightVal[1]);
最后 獲取根節(jié)點(diǎn)的 狀態(tài)數(shù)組 res，然后返回 res 數(shù)組中的最大值即可。
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-852442.html
class Solution {
public int rob(TreeNode root) {
int[] res = new int[2];
res = robTree(root);
return Math.max(res[0],res[1]);
}
public int[] robTree(TreeNode root){
int[] res = new int[2];
if(root==null){
return res;
}
int[] leftVal = robTree(root.left);
int[] rightVal = robTree(root.right);
//res[0]表示偷當(dāng)前節(jié)點(diǎn),所能盜取的最高金額
//res[1]表示不偷當(dāng)前節(jié)點(diǎn),所能盜取的最高金額
res[0]= root.val+leftVal[1]+rightVal[1];//偷當(dāng)前節(jié)點(diǎn),則其子節(jié)點(diǎn)不能偷
//不偷當(dāng)前節(jié)點(diǎn),則其子節(jié)點(diǎn)可偷可不偷,由子節(jié)點(diǎn)偷或者不偷能帶來的最高金額決定
res[1]=Math.max(leftVal[0],leftVal[1])+Math.max(rightVal[0],rightVal[1]);
return res;
}
}參考：動(dòng)態(tài)規(guī)劃，房間連成樹了，偷不偷呢？| LeetCode：337.打家劫舍3_嗶哩嗶哩_bilibili文章來源地址http://www.zghlxwxcb.cn/news/detail-852442.html
到了這里，關(guān)于LeetCode 337. 打家劫舍 III的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
