乐趣区

关于leetcode:LeetCode-337-打家劫舍-III-Python

337. 打家劫舍 III


题目起源:力扣(LeetCode)https://leetcode-cn.com/problems/house-robber-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.

解题思路


这道题是【198. 打家劫舍】、【213. 打家劫舍 II】的后续

思路:递归、动静布局

在这道题当中,偷窃的对象不再是一条街或者围成圈的屋宇。而是看似二叉树排布的屋宇。在这里,咱们会用动静布局的办法来解决。

不过在此之前,咱们先看题目,【如果两个间接相连的房子在同一天早晨被打劫,屋宇将主动报警】,这里的意思是,不可能偷窃相连的两个节点,也就是不能同时偷窃属于父子关系的节点。

题目给定的二叉树中,节点上的权值也就是要偷窃的金额,依照下面的条件,也就是说,每个节点都有两种状态:已偷取、未偷取。因为不能同时偷窃属于父子关系的节点,求该条件限定下,能偷取的金额最大值为多少。

递归

在这里,咱们先用递归的办法来解决,这里依据下面的剖析,分状况来探讨,具体思路如下(基于三层的二叉树形容):

  • 当偷窃根节点时,则无奈偷窃根节点下的左右子节点,然而能够抉择投左右子节点下的子树。
  • 当不偷窃根节点时,则能够思考偷窃根节点下的左右子节点。

那么,大抵的代码如下:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        # 分状况
        # 偷窃根节点 与 不偷窃根节点
        in_root = root.val
        if root.left:
            # 偷窃根节点时,无奈偷取子节点,那么偷窃子孙节点
            in_root += self.rob(root.left.left) +self. rob(root.left.right)
        if root.right:
            in_root += self.rob(root.right.left) +self. rob(root.right.right)
        
        # 不偷取根节点,那么收益就是左右子节点权值的总和
        not_in_root = self.rob(root.left) + self.rob(root.right)

        # 返回大值
        return max(in_root, not_in_root)

下面这段代码执行后超时,因为在计算子孙节点的时候,计算了根节点下的左右子树,而后续计算又反复计算了子孙节点。在这里,咱们来进行优化,将计算后的后果存储到哈希表中,遇到须要反复计算的局部,间接拿过去,不须要再次递归计算。

优化后代码见【代码实现 # 递归(优化)】

动静布局

从下面递归的办法中,咱们能够发现,最终最大收益为 in_root 和 not_in_root 的最大值。

也就是说,每个子树都有最优解:偷窃根节点 和 不偷窃根节点下的最优解。

咱们从新定义这个问题,每个节点能够抉择偷或者不偷,那么相连节点不能一起偷,那么:

  • 如果以后节点抉择偷窃时,左右子节点不抉择偷;
  • 如果以后节点抉择不偷时,左右子节点次要能取得最优解就行。

定义数组存储两个状态,索引 0 示意不偷,索引 1 示意偷。那么每个节点能偷到最大金额可定义为:

  • 以后节点抉择偷窃时,最大金额数 = 左子节点不偷能取得的最大金额 + 右子节点不偷能取得的最大金额 + 以后节点的金额
  • 以后节点抉择不偷时,最大金额 = 左子节点能偷的最大金额 + 右子节点能偷的最大金额。

那么相应的转移公式为:

# 以后节点不偷
ans[0] = max(rob(root.left)[0], rob(root.left)[1])
       + max(rob(root.right)[0], rob(root.right)[1])
# 以后节点抉择偷
ans[1] = rob(root.left)[0] + rob(root.right)[0] +  root.val

具体代码见【代码实现 # 动静布局】

代码实现


# 递归(优化)# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        # 存储计算过的后果
        hash_map = {}
        def helper(root):
            if not root:
                return 0
            # 如果存在于哈希表中,间接拿过去用
            if root in hash_map:
                return hash_map[root]
            in_root = root.val
            if root.left:
                # 偷窃根节点时,无奈偷取子节点,那么偷窃子孙节点
                in_root += helper(root.left.left) +helper(root.left.right)
            if root.right:
                in_root += helper(root.right.left) +helper(root.right.right)

            # 不偷取根节点,那么收益就是左右子节点权值的总和
            not_in_root = helper(root.left) + helper(root.right)
            ans = max(in_root, not_in_root)
            # 这里计算完之后,将后果存入哈希表中
            hash_map[root] = ans
            return ans
        return helper(root)

# 动静布局
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        def helper(root):
            if not root:
                return [0, 0]
            
            ans = [0, 0]

            left = helper(root.left)
            right = helper(root.right)

            # 两个索引对应两种状态,索引 0 示意不偷,索引 1 示意偷
            ans[0] = max(left[0], left[1]) + max(right[0], right[1])
            ans[1] = left[0] + right[0] + root.val

            return ans
        
        ans = helper(root)
        return max(ans[0], ans[1])

实现后果


欢送关注


公众号【书所集录】

退出移动版