打家劫舍III

题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

Code

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

Code

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

设每个节点有选择和不被选择两种情况，$f(o)$ 表示选择该节点，$g(o)$表示不选中该节点。

则$f(o) = g(r)+g(l)$b表示选择了o之后，left和right就不能选择了；

$g(o)=Math.max(g(l),f(l))+Math.max(g(r),f(r))$

通过候选遍历完成计算。

代码

java


*java*
/**
 \* Definition for a binary tree node.
 \* public class TreeNode {
 \*   int val;
 \*   TreeNode left;
 \*   TreeNode right;
 \*   TreeNode(int x) { val = x; }
 \* }
 */
class Solution {
  Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
  Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();  
  
  public void dfs(TreeNode node){
    if(node==null){
      return ;
    }
    dfs(node.left);
    dfs(node.right);
    f.put(node, node.val+g.getOrDefault(node.left, 0)+g.getOrDefault(node.right, 0));
    g.put(node, Math.max(g.getOrDefault(node.left, 0), f.getOrDefault(node.left,0))+Math.max(g.getOrDefault(node.right,0), f.getOrDefault(node.right, 0)));
  }
  
  public int rob(TreeNode root) {
    if(root==null){
      return 0;
    }
    dfs(root);
    return Math.max(g.getOrDefault(root, 0), f.getOrDefault(root,0));
    
  }
}