算法---LeetCode 337. 打家劫舍 III

1. 題目

原題連結

在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且隻有一個“父“

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

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

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

Related Topics 樹 深度優先搜尋

👍 692 👎 0

2. 題解

2.1 解法1: 動态規劃

設

1. f(o) 表示選擇 o節點的情況下，o節點的子樹上被選擇的節點的最大權值和；

2. g(o)表示不選擇 o節點的情況下，o節點的子樹上被選擇的節點的最大權值和；

   l和 r代表 o 的左右孩子。

則有:

1. 當 o 被選中時，o 的左右孩子都不能被選中，故 oo 被選中情況下子樹上被選中點的最大權值和為 l 和 r 不被選中的最大權值和相加，

   即

   f(o) = g(l) + g(r)

   。

2. 當 o 不被選中時，o 的左右孩子可以被選中，也可以不被選中。對于 oo 的某個具體的孩子 xx，它對 o 的貢獻是 x 被選中和不被選中情況下權值和的較大值。

   故

   g(o)=max{f(l),g(l)}+max{f(r),g(r)}

   。

class Solution {
        Map<TreeNode, Integer> fMap = new HashMap<>();
        Map<TreeNode, Integer> gMap = new HashMap<>();

        public int rob(TreeNode root) {
            dfs(root);
            return Math.max(fMap.getOrDefault(root, 0), gMap.getOrDefault(root, 0));
        }

        public void dfs(TreeNode root) {
            if (root == null) {
                return;
            }
            dfs(root.left);
            dfs(root.right);
            fMap.put(root, root.val + gMap.getOrDefault(root.left, 0) + gMap.getOrDefault(root.right, 0));
            int left = Math.max(fMap.getOrDefault(root.left, 0), gMap.getOrDefault(root.left, 0));
            int right = Math.max(fMap.getOrDefault(root.right, 0), gMap.getOrDefault(root.right, 0));
            gMap.put(root, left + right);

        }
    }
           

參考題解:

官方題解