資訊專欄INFORMATION COLUMN
摘要：一番偵察之后，聰明的小偷意識(shí)到這個(gè)地方的所有房屋的排列類似于一棵二叉樹。如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。
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.
描述
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。
計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。
示例 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.
思路
用一個(gè)包含兩個(gè)元素的數(shù)組 result ，result[0] 表示偷當(dāng)前節(jié)點(diǎn)的房子，result[1] 表示不偷當(dāng)前節(jié)點(diǎn)的房子。
如果偷當(dāng)前的房子，那么 result[0] = 當(dāng)前節(jié)點(diǎn)的值 + max(左右子樹中，不偷根節(jié)點(diǎn)房子可以獲得的最大值)。
如果不偷當(dāng)前的房子，那么 result[1] = max(左子樹中偷或不偷根節(jié)點(diǎn)房子可以獲得的最大值) + max(右子樹中偷或不偷根節(jié)點(diǎn)房子可以獲得的最大值)
最后可以獲得的最大值值為 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] 表示偷當(dāng)前的房子，result[1] 表示不偷當(dāng)前的房子
if not root: return [0, 0]
result = [0, 0]
left = self.recursion(root.left)
right = self.recursion(root.right)
# 偷當(dāng)前的房子：result[0] ：當(dāng)前節(jié)點(diǎn)的值+ 左右子樹中不偷根節(jié)點(diǎn)房子的最大值
result[0] = root.val + left[1] + right[1]
# 不偷當(dāng)前的房子：result[1] 那么左右子樹的根節(jié)點(diǎn)偷不偷都可以，選最大值
result[1] = max(left[0], left[1]) + max(right[0], right[1])
return result
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來(lái)源 ，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/43542.html
摘要：復(fù)雜度思路對(duì)于每一個(gè)位置來(lái)說(shuō)，考慮兩種情況分別對(duì)和再進(jìn)行計(jì)算。用對(duì)已經(jīng)計(jì)算過的進(jìn)行保留，避免重復(fù)計(jì)算。 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...
摘要：題目要求即如何從樹中選擇幾個(gè)節(jié)點(diǎn)，在確保這幾個(gè)節(jié)點(diǎn)不直接相連的情況下使其值的和最大。當(dāng)前節(jié)點(diǎn)的情況有兩種選中或是沒選中，如果選中的話，那么兩個(gè)直接子節(jié)點(diǎn)將不可以被選中，如果沒選中，那么兩個(gè)直接子節(jié)點(diǎn)的狀態(tài)可以是選中或是沒選中。 題目要求 The thief has found himself a new place for his thievery again. There is on...
摘要：解法真的非常巧妙，不過這道題里仍要注意兩個(gè)細(xì)節(jié)。中，為時(shí)，返回長(zhǎng)度為的空數(shù)組建立結(jié)果數(shù)組時(shí)，是包括根節(jié)點(diǎn)的情況，是不包含根節(jié)點(diǎn)的情況。而非按左右子樹來(lái)進(jìn)行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...
摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問題一般化，然后再找到初始情況開始這個(gè)由一般到特殊的計(jì)算過程。 House Robber I You are a professional robber planning to rob houses along a street. Each...
摘要：注意對(duì)邊界條件的判斷，是否非空，是否長(zhǎng)度為 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...
閱讀 2818·2023-04-25 22:51
閱讀 2057·2021-10-11 10:58
閱讀 3316·2019-08-30 10:49
閱讀 1877·2019-08-29 17:09
閱讀 3141·2019-08-29 10:55
閱讀 847·2019-08-26 10:34
閱讀 3492·2019-08-23 17:54
閱讀 985·2019-08-23 16:06
