337. 打家劫舍 III（递归）-蒲公英云

337. 打家劫舍 III（递归）

男娘i 2023-10-05 17:48 92阅读 0赞

337. 打家劫舍 III

题目
解题思路
代码

题目

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

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
在这里插入图片描述

解题思路

先把题目用一句话概括一下：就是要间隔遍历。

因为入口只有根节点，所以我们对于根节点来说只有两种选择。
偷或者不偷。 对于根节点的选择，会影响子节点的状态。

所以我们只需要考虑两种情况：
①偷根节点。
在这里插入图片描述

②不偷根节点。
在这里插入图片描述

2021/4/23二刷，发现直接暴力已经行不通了，故而加个备忘录进行优化。

代码

class Solution {
    Map<TreeNode,Integer> map=new HashMap<>();
    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        int val1=root.val;//第一种情况，偷根节点root
        if(root.left!=null){
    //对左子树来说
            // 如果根节点被偷了，且根节点的左子树不为0，那么就可以偷根节点的孙子节点
            val1=val1+rob(root.left.left)+rob(root.left.right);
        }
        if(root.right!=null){
    //对右子树来说
            // 如果根节点被偷了，且根节点的右子树不为0，那么就可以偷根节点的孙子节点
            val1=val1+rob(root.right.left)+rob(root.right.right);
        }       
        int val2=rob(root.left)+rob(root.right);//第二种情况，不偷根节点，那么为了偷取的金额最高，就去偷它的子节点
        map.put(root,Math.max(val1,val2));
        return Math.max(val1,val2);//看看两种情况那个偷的钱更多
    }
}