在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

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

class Solution:def rob(self,root:TreeNode)->int:def dfs(node):if not node:return [0, 0]left = dfs(node.left)right = dfs(node.right)dp = [0,0]dp[0] = max(left)+max(right)dp[1] = left[0]+right[0]+node.valreturn dpreturn max(dfs(root))

總結(jié)

以上是生活随笔為你收集整理的[leetcode] 337.打家劫舍3的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。