leetcode 337.打家劫舍 III

leetcode 337.打家劫舍 III

题目描述

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

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
示例 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.

递归

【打家劫舍 I】和【打家劫舍 II】都是基于数组的。
而这道题是基于二叉树的。

我们把房子按照二叉树的结构排列好,然后按层横切一刀并记录下每层的编号

仔细看题目中的这句话:如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。能直接相连的只有父子节点,兄弟节点是不相连的。
所以这句话的意思是偷了父节点,那么子节点就不能偷了,但还可以继续偷孙子节点。即偷了

第 i层,那么第i-1i+1层就不能偷了。
比如我偷第2层,也就是上图中23两个节点。那么第1层的1和第3层的4567都不能偷了。

注意,这道题跟【打家劫舍 I】、【打家劫舍 II】一样,不能简单的值判断奇偶下标,奇偶层数,比如下图这样就不是按照奇偶层数来的

如何用递归去实现呢?
我们先从根节点分析,对于根节点来说,只有两种选择,或者不偷
根节点的这两个选择,会导致它的两个孩子出现三种选择:

1、父节点(也就是根节点)选择,那么两个孩子23也就只能选不偷
2、父节点选择不偷,两个孩子可以选择
3、父节点选择不偷,两个孩子依然可以选择不偷

对于根节点的左孩子2的两种选择也会导致它的孩子45出现三种状态

1、2选择偷,45只能选择不偷
2、2选择不偷,45可以选择偷
3、2选择不偷,45也可以选择不偷

根节点的右孩子3也是一样的

1、3选择偷,67只能选择不偷
2、3选择不偷,67可以选择偷
3、3选择不偷,67也可以选择不偷

根节点的左孩子的左孩子4 依然是这样

所以,对于任意节点来说,有三种状态

1、如果父节点选择,那么本节点只能选择不偷
2、如果父节点选择不偷,那么本节点可以选择
3、如果父节点选择不偷,那么本节点依旧可以选择不偷

那么递归逻辑就可以这么实现:

if(父节点选择偷):
    a = 获取左孩子的最大值(本节点不偷) + 获取右孩子的最大值(本节点不偷)
else(父节点选择不偷):
    b = 获取左孩子的最大值(本节点偷) + 获取右孩子的最大值(本节点偷) + 本节点的值
    c = 获取左孩子的最大值(本节点不偷) + 获取右孩子的最大值(本节点不偷)
返回 max(a,b,c)

父节点选择偷/不偷,可以作为状态参传入即可。
这里我们还可以把c单独领出来,不放到if-else里面,即表示什么也不干

java代码:

class Solution {
    public int rob(TreeNode root) {
        if(root==null) {
            return 0;
        }
        return dfs(root,0);
    }
 
    private int dfs(TreeNode root,int status) {
        if(root==null) {
            return 0;
        }
        int a=0,b=0,c=0;
        //不管父节点选择偷/不偷,本次什么都不干
        a = dfs(root.left,status)+dfs(root.right,status);
        //父节点选择偷,本次不偷   
        if(status==1) {
            b = dfs(root.left,0)+dfs(root.right,0);
        }
        //父节点选择不偷,本次选择偷
        else {
            c = dfs(root.left,1)+dfs(root.right,1)+root.val;
        }
        //返回三种状态的最大值
        return Math.max(a,Math.max(b,c));
    }
} 
                                                                                          

python代码:

class Solution(object):
    def rob(self, root):
        if not root:
            return 0
        def dfs(root,status):
            if not root:
                return 0
            a,b,c = 0,0,0
            # 不管父节点选择偷/不偷,本次什么都不干
            a = dfs(root.left,status)+dfs(root.right,status)
            # 父节点选择偷,本次不偷 
            if status:
                b = dfs(root.left,0)+dfs(root.right,0)
            # 父节点选择不偷,本次选择偷                
            else:
                c = dfs(root.left,1)+dfs(root.right,1)+root.val
            # 返回三种状态的最大值    
            return max(a,b,c)
        return dfs(root,0)
                                                                                       

递归+记忆化

这里的记忆化跟一维数组不同,一维数组的递归+记忆化,从调用上来说,就是去掉重复的分支调用(剪枝)。
而在一颗二叉树上再做递归,就不是剪枝,而是减少某个节点的反复调用次数。

以上图10这个节点为例
从1->2->5->10 这个调用关系来看,每个节点都会经历偷/不偷这样的状态
而由此会引发10这个节点被反复调用很多次

假设根节点1要计算这个状态下的最大值,此时10这个节点会被反复第调用好几次

再假设根节点1要计算不偷这个状态下的最大值,此时10 这个节点仍旧会被反复调用很多次

对于10这个节点来说,只需要计算不偷两种状态下的最大值即可,剩下的那些都是重复的调用,所以可以用缓存记录下这两种状态的最大值,这样就可以省掉大量的重复计算。

java代码:

class Solution {
    public int rob(TreeNode root) {
        if(root==null) {
            return 0;
        }
        //缓存的key是TreeNode和状态的组合,这里将TreeNode和status封装成一个Pair对象作为key
        Map<Pair,Integer> cache = new HashMap<Pair,Integer>();
        return dfs(cache,root,0);
    }
 
    private int dfs(Map<Pair,Integer> cache,TreeNode root,int status) {
        if(root==null) {
            return 0;
        }
        //创建一个Pair对象作为key,key的内容是TreeNode和status组合
        Pair p = new Pair(root,status);
        if(cache.containsKey(p)) {
            return cache.get(p);
        }
        //后面的逻辑跟递归版本是一样的
        int a=0,b=0,c=0;
        a = dfs(cache,root.left,status)+dfs(cache,root.right,status);
        if(status==1) {
            b = dfs(cache,root.left,0)+dfs(cache,root.right,0);
        }
        else {
            c = dfs(cache,root.left,1)+dfs(cache,root.right,1)+root.val;
        }
        //将Pair和最大值缓存起来
        cache.put(p,Math.max(a,Math.max(b,c)));
        return cache.get(p);
    }
    //这里自定义一个Pair对象,用来封装TreeNode和status,Pair作为哈希表的key
    //同时还需要重新定义Pair的hashCode()和equals()两个函数
    class Pair {
        TreeNode root;
        int status;
        Pair(TreeNode root,int status) {
            this.root = root;
            this.status = status;
        }
        public int hashCode() {
            return root.hashCode()+status;
        }
  
        public boolean equals(Object obj) {
            if(obj==null) {
                return false;
            }
            Pair p = (Pair)obj;
            if(p.root.hashCode()==root.hashCode() && p.status==status) {
                return true;
            }
            return false;
        }
    }
} 
                                                                                            

python代码:

class Solution(object):
    def rob(self, root):
        if not root:
            return 0
        # 创建一个缓存省去重复调用    
        cache = dict()
        # 这里的逻辑跟递归版本一样,只是加上了缓存
        def dfs(root,status):
            if not root:
                return 0
            if (root,status) in cache:
                return cache[root,status]
            a,b,c = 0,0,0
            a = dfs(root.left,status)+dfs(root.right,status)
            if status:
                b = dfs(root.left,0)+dfs(root.right,0)
            else:
                c = dfs(root.left,1)+dfs(root.right,1)+root.val
            cache[root,status] = max(a,b,c)
            return cache[root,status]
        return dfs(root,0)
                                                                                  

动态规划

这道题是树形DP问题
递归解法中中我们是自顶向下的方式求解的,而动态规划中我们采用自底向上的方式。

假设要求下图中橙色1这个节点最大值,我们可以这么做

1、求出橙色1的四个孙子节点最大值的累加,再加上橙色节点1本身的值,记做a
2、求出橙色1的两个孩子节点的最大值的累加,记做b

那么橙色节点1的最大值就是max(a,b)
但是光求出这个值还是少点了,为什么呢?
假设橙色节点还有一个父节点,也就是下图中的绿色节点

绿色节点的最大值
1、橙色节点1的两个孩子节点最大值累加,再加上节点a的两个孩子最大值累加,加上绿色节点本身,将这个值记做x
2、橙色节点1的最大值,加上节点a的最大值,记做y
绿色节点的最大值就是max(x,y)

所以对于任意节点来说,我们需要返回两个值

一个值是当前节点本身的最大值a,对应的是上图中第i层的4
另一个是孩子节点累加后的最大值b,对应的是第i+1层4的两个孩子
因为计算第i-1层的某个节点时,需要用到 第i层 和 第i+1层 的值
第i层4的返回值会被第i-1层的5和第i-2层的2用到

整个计算过程如下,下图中的执行过程和代码中真实的执行逻辑有些差别,我做了一些简化,但所表达的求解思路是类似的

java代码:

class Solution {
    public int rob(TreeNode root) {
        if(root==null) {
            return 0;
        }
        Pair p = dfs(root);
        return Math.max(p.v1,p.v2);
    }
 
    private Pair dfs(TreeNode root) {
        //如果节点为空就返回(0,0)第一个0表示当前节点的最大值,第二个0表示所有子节点的最大值
        if(root==null) {
            return new Pair(0,0);
        }
        //获取左右节点的值,这里会拿到四个值,左节点的值,左节点孩子的值,右节点的值,右节点孩子的值
        //pleft.v1,pleft.v2,pright.v1,pright.v2
        Pair pleft = dfs(root.left);
        Pair pright = dfs(root.right);
        //pleft.v2表示left的所有所有子节点,a就是当前节点的值+孙子节点的值
        int a = pleft.v2+pright.v2+root.val;
        //b就是两个孩子节点的值 
        int b = pleft.v1+pright.v1;
        //当前节点的最大值就是max(a,b),同时还要返回子节点的最大值,因为当前节点的父节点会用到
        Pair res = new Pair(Math.max(a,b),b);
        return res;
    }
   //自定义的Pair对象,封装了两个整数作为返回值
    class Pair {
        //v1表示当前节点的最大值,v2表示所有子节点的最大值
        int v1;
        int v2;
        Pair(int v1,int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }
    }
} 
                                                                                              

python代码:

class Solution(object):
    def rob(self, root):
        if not root:
            return 0
        def dfs(root):
            # 如果节点为空就返回(0,0)第一个0表示当前节点的最大值,第二个0表示所有子节点的最大值
            if not root:
                return 0,0
            # 获取左右节点的值,这里会拿到四个值,左节点的值,左节点孩子的值,右节点的值,右节点孩子的值
            left,left_pre = dfs(root.left)
            right,right_pre = dfs(root.right)
            # a就是当前节点的值+孙子节点的值
            a = left_pre+right_pre+root.val
            # b就是两个孩子节点的值 
            b = left+right
            # 当前节点的最大值就是max(a,b),同时还要返回子节点的最大值,因为当前节点的父节点会用到
            return max(a,b),b
        a,b = dfs(root)
        return max(a,b)
                                                                                                         

3 次阅读

发表评论

电子邮件地址不会被公开。