LeetCode 337. House Robber III

ymyang 发布于2019-07-31 10:16 / 1199人阅读

摘要：一番侦察之后，聪明的小偷意识到这个地方的所有房屋的排列类似于一棵二叉树。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]

     3
    / 
   2   3
        
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / 
   4   5
  /     
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

描述

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

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

示例 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.

思路

用一个包含两个元素的数组 result ，result[0] 表示偷当前节点的房子，result[1] 表示不偷当前节点的房子。

如果偷当前的房子，那么 result[0] = 当前节点的值 + max(左右子树中，不偷根节点房子可以获得的最大值)。

如果不偷当前的房子，那么 result[1] = max(左子树中偷或不偷根节点房子可以获得的最大值) + max(右子树中偷或不偷根节点房子可以获得的最大值)

最后可以获得的最大值值为 max(result)

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-04-07 10:43:47
# @Last Modified by:   何睿
# @Last Modified time: 2019-04-07 11:00:22


class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.recursion(root))

    def recursion(self, root):
        # result[0] 表示偷当前的房子，result[1] 表示不偷当前的房子
        if not root: return [0, 0]
        result = [0, 0]
        left = self.recursion(root.left)
        right = self.recursion(root.right)
        # 偷当前的房子：result[0] ：当前节点的值+ 左右子树中不偷根节点房子的最大值
        result[0] = root.val + left[1] + right[1]
        # 不偷当前的房子：result[1] 那么左右子树的根节点偷不偷都可以，选最大值
        result[1] = max(left[0], left[1]) + max(right[0], right[1])
        return result

源代码文件在这里。
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

服务器托管混合云 Robber House ee337新域名 III

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43542.html

LeetCode[337] House Robber III

摘要：复杂度思路对于每一个位置来说，考虑两种情况分别对和再进行计算。用对已经计算过的进行保留，避免重复计算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...

Dr_Noooo 2019-08-14 15:00 评论0 收藏0
leetcode337. House Robber III

摘要：题目要求即如何从树中选择几个节点，在确保这几个节点不直接相连的情况下使其值的和最大。当前节点的情况有两种选中或是没选中，如果选中的话，那么两个直接子节点将不可以被选中，如果没选中，那么两个直接子节点的状态可以是选中或是没选中。题目要求 The thief has found himself a new place for his thievery again. There is on...

AlphaWallet 2019-08-16 11:14 评论0 收藏0
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 评论0 收藏0
leetcode198,213 house robber

摘要：你不能连着偷两家因为这样会触发警报系统。现在有一个数组存放着每一家中的可偷金额，问可以偷的最大金额为多少这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

whidy 2019-08-16 11:01 评论0 收藏0
[LeetCode] House Robber I II

摘要：注意对边界条件的判断，是否非空，是否长度为 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

qpal 2019-08-14 15:17 评论0 收藏0