深度优先遍历--最大路径和

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

导读：首先是树的建立 class TreeNode: def __init__ (self,x,left=None,right= None): self.val = x self.left = left self.right = rightt3 =TreeNode(10);t4=TreeNode(12 )t5 =TreeNode(2);t6=TreeNode(1 )t1 =TreeNode(2,t3,t4);t2=TreeNode(-2 ,t5,t6)root =T

首先是树的建立

class TreeNode:
    def __init__(self,x,left=None,right=None):
        self.val=x
        self.left=left
        self.right=right
t3=TreeNode(10);t4=TreeNode(12)
t5=TreeNode(2);t6=TreeNode(1)
t1=TreeNode(2,t3,t4);t2=TreeNode(-2,t5,t6)
root=TreeNode(1,t1,t2)

树如图所示：

对于每一个节点而言，都有一个停值和不停值，当前节点的停值=max(左孩子停值，左孩子不停值，右孩子停值，右孩子不停值，左孩子不停值+右孩子不停值+当前节点的值)；

当前节点的不停值=max(左孩子不停值+当前节点值，右孩子不停值+当前节点值，当前节点值)

def maxpathsum(root):
    return max(helper(root))
 helper(root):
    if root == None:
        #如果是空，那么返回无穷小，这样叶子节点才会有相应的值
        return float("-inf"),float(")
    leftno,leftstop=helper(root.left)
    rightno,rightstop=helper(root.right)
    nostop=max(leftno+root.val,rightno+root.val,root.val)
    stop=max(leftno,leftstop,rightno,rightstop,leftno+rightno  
    +root.val)
    return nostop,stop

注意：我们利用深度优先搜索一直到叶子节点，然后从下至上依此获取每个节点的停值和不停值。

（编辑：李大同）

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