337. 打家劫舍 III（递归）

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

#### 337. 打家劫舍 III ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

## 解题思路 ##

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

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

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

②不偷根节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]

--------------------

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);//看看两种情况那个偷的钱更多
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210114215143538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021011421591347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210114220059795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70