题解 | #打家劫舍(三)#
打家劫舍(三)
http://www.nowcoder.com/practice/82b6dce6a7634419b272ee4397e26d89
动态规划，单看一个二叉树结构，当前节点取得最大值分为偷或不偷两种情况，取决于左右两边是否偷了
每次计算返回当前节点偷和不偷分别能够取得的最大值
- 当前节点偷：则左右两边都不能偷,即：
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
