深度优先遍历--怎么抓住小偷

概述怎么抓住小偷

问题描述：每栋别墅以二叉树的结构建立，每个节点的值是财富值，小偷不能够偷相接的别墅，问小偷最多能够偷多少财富值?

 

有个规律：每一个节点的偷值都是：左侧子节点的不偷值+右侧子节点的不偷值+该节点的值；不偷值：左侧子节点的最大值+右侧子节点的最大值。我们可以先深度优先遍历到每一个叶子节点，再依此计算。

class TreeNode:    de __init(self,x,left=None,right=None):        self.val=x        self.left=left        self.right=rightt3=TreeNode(1);t4=TreeNode(3);t6=TreeNode(1)t1=TreeNode(4,t3,t4);t2=TreeNode(5,left=None,1)">t6)root=TreeNode(3,t1,t2)def rob(root):    a=helper(root)    return max(a[0],a[])def helper(root):    if root == None:        return (0,0)    left=helper(root.left)    right=helper(root.right)    robval=rot.val+left[1]+right[]    skipval=max(left[1])+max(right[])    return (robval,skipval)
输出：9

 

主要考察建模能力以及实现能力。

 

总结

以上是内存溢出为你收集整理的深度优先遍历--怎么抓住小偷全部内容，希望文章能够帮你解决深度优先遍历--怎么抓住小偷所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。