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