vlambda博客
学习文章列表

有一个绝顶狡猾的小偷瞄准了一个高档小区。如图1所示，这个小区的别墅以二叉树的结构坐落。除了第一栋别墅，每一栋别墅都与另一栋“源头”别墅连接。一旦小偷闯入两栋相接的别墅，警铃就会被触发。圆圈里的数字代表财产，狡猾的小偷已经计划好了路线，准备在不触发警报的前提下偷最多的钱。别墅小区的保安部门最近得到了风声，说有一个世纪大盗瞄上了别墅区。据说此小偷神无踪影，武功高强，所以保安打算在小偷的必经之路上布置警卫，不动声色地抓住小偷。问题是，小偷会怎么选路线呢？

如下图所示，小偷肯定会选择灰色的这两栋别墅，偷到4+5=9 万元。在这一节中，我们写一个程序来输出小偷经过路线上的金额总和。

再来看一个例子，如果别墅布置如图所示，那么小偷肯定会闯入以下三栋别墅，得到3+3+1=7万元

解题思路

首先，我们分析一下前提条件。前面说到两栋相连的别墅被盗时警铃会被触发。如图4所示，把二叉树分层。

如果小偷闯入第一层，那么他就不能偷第二层的房子。他可以选择偷第三层或第四层的房子。小偷需要统观全局，因为他在每一层的决定都影响下一层。如图所示，小偷有不同的选择方案。

在每一个节点，小偷都需要做一个选择：偷还是不偷。小偷需要比较如果偷能得到多少钱和不偷能得到多少钱。如果偷了这个节点，这个节点的子节点就不能再偷了。

让我们给每一个节点两个值：偷得到的钱和不偷得到的钱。如图所示，例子中的每一个节点旁边都有偷：0与不偷：0两个值。让我们从底层开始，更改节点4、5和6的值。如果偷，得到相对应的钱；如果不偷，则得到0。

如图所示，上移一层，设节点2与节点3的值。在节点2，如果偷，小偷将会得到4万元，但与节点4与节点5的钱无缘；如果不偷，小偷可以偷节点4与节点5的钱，得到4万元。再看节点3，如果偷，小偷得到5万元；如果不偷，小偷得到节点6的1万元。

如图所示，设根节点1的值。如果偷，将会得到节点1的3万元、节点4与节点5的4万元，以及节点6的1万元；

如果不偷，可以得到节点2的4万元，以及节点3的5万元。权衡金额，小偷应该会采取下图所示的两个措施之一。

在以上的分析中我们发现了一个规律。每一个节点的偷值都是：左侧子节点的不偷值+右侧子节点的不偷值+节点的财富；每一个节点的不偷值都是：左侧子节点的最大值+右侧子节点的最大值。比如，节点1的偷值是4（节点2的不偷值）+1（节点3的不偷值）+3（节点1的财富）。节点1的不偷值是4（节点2的最大值）+5（节点3的最大值）。

如果节点的定义为：

class TreeNode:							#二叉树节点的定义
     def __init__(self, x):
         self.val = x							#财富值
         self.left = None						#左侧子节点
         self.right = None					#右侧子节点

那么任何一个节点（用root表示）的偷值（robValue）与不偷值（skipValue）则是：

robValue = root.val + root.left.skipValue +  root.right.skipValue
skipValue=max(root.left.robValue,root.left.skipValue)+   
max(root.right.robValue,root.right.skipValue)

现在需要解决的问题是：如何得到子节点的偷值与不偷值，也就是说，如何得到 root.left.robValue、root.left.skipValue、root.right.robValue 与root.right.skipValue。

答案很简单，找到子节点的子节点的偷值与不偷值就可以了，也就是说，root.left.left.robValue、root.left.left.skipValue、root.left.right.robValue、root.left.right.skipValue、root.right.left.robValue……即利用递归来深度优先遍历二叉树。

从思路到代码

现在我们尝试把之前的思路写出来

 def rob(self, root):
        a = self.helper(root)	#a是一个二维数组，为root的[偷值，不偷值]
        return max(a[0],a[1])	#返回两个值的最大值，此值为小偷最终获得的财富值。
    def helper(self,root): #参数为root节点，helper方法输出一个二维数组：root节点的[偷值，不偷值]
        if(root==None):		#如果root节点为空，输出[0,0]
            return [0,0]
        left = self.helper(root.left)  #left是一个二维数组，为root左侧子节点的[偷值，不偷值]
        right = self.helper(root.right) #right也是一个二维数组，为root右侧子节点的[偷值，不偷值]
        robValue = root.val + left[1]+ right[1]		#root的偷值
        skipValue = max(left[0],left[1]) + max(right[0],right[1])	#root的不偷值
        return [robValue, skipValue]				#输出小偷可获得的最大金额

划重点

抓小偷问题本质上是树的深度优先遍历问题。通过递归求解左右子树来求解最终问题。

长按识别下方二维码，和众多位岛民一起

把别人的顿悟，变成你的基本功

 花半秒钟就看透事物本质的人，
  和花一辈子都看不清的人，
  注定是截然不同的命运。