题解 | #打家劫舍(三)#

动态规划，单看一个二叉树结构，当前节点取得最大值分为偷或不偷两种情况，取决于左右两边是否偷了

每次计算返回当前节点偷和不偷分别能够取得的最大值

• 当前节点偷：则左右两边都不能偷,即：

yes=no左+no右+当前值

• 当前节点不偷：则左右两边都偷了，或都不偷，或左右只有一个偷了,即：

no=max(no左+no右,yes左+yes右,yes左+no右,no左+yes右)

然后更新最大收益:

maxVal=max(yes,no) 代码如下

global maxVal
maxVal=0#初始化为0
def walk(node):
    global maxVal
    if node is None:
        return 0,0#偷了还是没偷，都是0
    yes_l,no_l=walk(node.left)
    yes_r,no_r=walk(node.right)
    yes=no_l+no_r+node.val
    no=max(yes_l+yes_r,no_l+no_r,yes_l+no_r,yes_r+no_l)
    maxVal=max(yes,no)
    return yes,no
    
class Solution:
    def rob(self , root: TreeNode) -> int:
        walk(root)
        return maxVal