力扣(LeetCode)377

cnio 發(fā)布于2019-08-16 15:37 / 2255人閱讀

摘要：如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。若偷根節(jié)點(diǎn)，則偷盜數(shù)額等于左子樹(shù)的左右子樹(shù)偷盜最大值右子樹(shù)的左右子樹(shù)偷盜最大值。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹(shù)”。如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。

計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。

示例 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.

解答：
只要比較偷根節(jié)點(diǎn)和不偷根節(jié)點(diǎn)哪個(gè)值大即可。
若偷根節(jié)點(diǎn)，則偷盜數(shù)額等于root.val+左子樹(shù)的左右子樹(shù)偷盜最大值+右子樹(shù)的左右子樹(shù)偷盜最大值。
若不偷根節(jié)點(diǎn)，則偷盜數(shù)額等于左子樹(shù)的偷盜最大值+右子樹(shù)的偷盜最大值。

java ac代碼：
/**

Definition for a binary tree node.

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

*/
class Solution {

public int rob(TreeNode root) {
    //若偷根，則只能偷左右子樹(shù)的左右子樹(shù)
    //若不偷根，則左右子樹(shù)都可以偷
    //比較兩者誰(shuí)大
    
    if(root == null)return 0;
    
    int temp = root.val;
    if(root.left != null)temp += rob(root.left.left)+rob(root.left.right);
    if(root.right != null)temp += rob(root.right.left)+rob(root.right.right);
    
    return Math.max(temp,rob(root.left)+rob(root.right));
}

}

不過(guò)這樣的復(fù)雜度過(guò)大，因?yàn)橛泻芏嗖襟E被重復(fù)計(jì)算。
添加一個(gè)HashMap記錄已經(jīng)存在的結(jié)果，這樣避免重復(fù)計(jì)算。
java ac代碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMapmap = new HashMap(1000);
    
    public int rob(TreeNode root) {
        //若偷根，則只能偷左右子樹(shù)的左右子樹(shù)
        //若不偷根，則左右子樹(shù)都可以偷
        //比較兩者誰(shuí)大
        
        if(root == null)return 0;
        if(map.containsKey(root))return map.get(root);
        int temp = root.val;
        if(root.left != null)temp += rob(root.left.left)+rob(root.left.right);
        if(root.right != null)temp += rob(root.right.left)+rob(root.right.right);
        
        int ans = Math.max(temp,rob(root.left)+rob(root.right));
        map.put(root,ans);
        return ans;
    }
}

這樣一來(lái)，速度快了很多，不過(guò)需要注意的是一般Map的key是類類型，需要重寫hashCode和equals方法。這里雖然沒(méi)寫，但是有可能是沒(méi)有產(chǎn)生hash沖突，或者是后臺(tái)已經(jīng)幫我們謝過(guò)了。