力扣 337. 打家劫舍III

前置

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

解法

def rob(root):
    # 后序遍历
    """
    0: 代表没偷
    1: 代表偷了
    """
    def fun(node):
        if not node: return 0, 0
        l_pre_dp0, l_pre_dp1 = fun(node.left)
        r_pre_dp0, r_pre_dp1 = fun(node.right)
        dp0 = max(l_pre_dp0, l_pre_dp1) + max(r_pre_dp0, r_pre_dp1)
        dp1 = node.val + l_pre_dp0 + r_pre_dp0
        return dp0, dp1
    
    return max(fun(root))