Skip to content

Latest commit

 

History

History
47 lines (28 loc) · 964 Bytes

337._house_robber_iii.md

File metadata and controls

47 lines (28 loc) · 964 Bytes

###337. House Robber III

题目: https://leetcode.com/problems/house-robber-iii/

难度: Medium

思路:

参考 https://www.hrwhisper.me/leetcode-house-robber-iii/

这个解法好像有点厉害

从root开始抢起来,最大能抢到的两个可能: 抢root和不抢root

  • rob_root = max(rob_L + rob_R , no_rob_L + no_nob_R + root.val)
  • no_rob_root = rob_L + rob_R

这个递归写起来就很厉害了

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root):
            if not root: return 0, 0
            rob_L, no_rob_L = dfs(root.left)
            rob_R, no_rob_R = dfs(root.right)
            return max(no_rob_R + no_rob_L + root.val , rob_L + rob_R), rob_L + rob_R

        return dfs(root)[0]

对于每个node,我们return的是从这个node能抢到的最大值,以及不抢它能获得的最大值,这个递归简直我服