337._house_robber_iii.md

###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能抢到的最大值，以及不抢它能获得的最大值，这个递归简直我服