LeetCode_BinaryTree_337. House Robber III 打家劫舍 III【動态規劃】【Java】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​三，AC代碼​​

​​Java​​

​​四，解題過程​​

​​第一搏​​

​​第二搏​​

一，題目描述

英文描述

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

中文描述

小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口，我們稱之為 root 。

除了 root 之外，每棟房子有且隻有一個“父“房子與之相連。一番偵察之後，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果 兩個直接相連的房子在同一天晚上被打劫 ，房屋将自動報警。

給定二叉樹的 root 。傳回 在不觸動警報的情況下 ，小偷能夠盜取的最高金額 。

示例與說明

​

連結：​​https://leetcode.cn/problems/house-robber-iii​​著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

參考官方題解​​@力扣官方題解【打家劫舍 III】​​

後序周遊+動态規劃，後序周遊指明了動态規劃的轉移順序。

聲明一個長度為2的數組記錄動态規劃過程中産生的值，其中位置0表示不選擇目前節點，1表示選擇目前節點；

先周遊左子樹得到左子樹的狀态數組leftTree，再周遊右子樹得到右子樹的狀态數組rightTree，最後可以得到目前節點的狀态數組ans

不選目前節點，左右子樹節點可選可不選（取兩種方案最大值）: 

• ans[0] = Math.max(leftTree[0], leftTree[1]) + Math.max(rightTree[0], rightTree[1])

選擇目前節點，左右兩子節點均不能選擇: 

• ans[1] = root.val + leftTree[0] + rightTree[0]

三，AC代碼

Java

class Solution {

    public int rob(TreeNode root) {
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }
    public int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        int[] leftTree = dfs(root.left);
        int[] rightTree = dfs(root.right);
        int[] ans = new int[2];
        
        ans[1] = root.val + leftTree[0] + rightTree[0];// 選擇root節點，則左右子樹節點不能被選中
        ans[0] = Math.max(leftTree[0], leftTree[1]) + Math.max(rightTree[0], rightTree[1]);// 不選root節點，左右子樹節點可選可不選（取兩種方案最大值）
        return ans;
    }
}      

四，解題過程

第一搏

後序周遊 + 雙hash表（分别記錄是否選擇目前節點下的情況）

class Solution {
    Map<TreeNode, Integer> choose = new HashMap<>();
    Map<TreeNode, Integer> notChoose = new HashMap<>();
    public int rob(TreeNode root) {
        choose.put(null, 0);
        notChoose.put(null, 0);
        dfs(root);
        return Math.max(choose.get(root), notChoose.get(root));
    }
    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);

        int ans = 0;
        ans = root.val + notChoose.get(root.left) + notChoose.get(root.right);
        choose.put(root, ans);

        int maxLeft = Math.max(choose.get(root.left), notChoose.get(root.left));
        int maxRight = Math.max(choose.get(root.right), notChoose.get(root.right));
        ans = maxLeft + maxRight;
        notChoose.put(root, ans);
    }
}      

第二搏

注意到後序周遊過程中，隻會用到目前節點左右兩子樹節點對應的狀态，是以遞歸傳回值可以用大小為2的數組代替，其中位置0表示不選擇目前節點，1表示選擇目前節點。

這樣遞歸過程将會變得更加簡潔