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

发布时间：2020-12-20 09:50:58 所属栏目：Python 来源：网络整理

导读：问题描述：每栋别墅以二叉树的结构建立，每个节点的值是财富值，小偷不能够偷相接的别墅，问小偷最多能够偷多少财富值? ? 有个规律：每一个节点的偷值都是：左侧子节点的不偷值+右侧子节点的不偷值+该节点的值；不偷值：左侧子节点的最大值+右侧子节点的最大

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

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

class TreeNode:
    de __init(self,x,left=None,right=None):
        self.val=x
        self.left=left
        self.right=right
t3=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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!