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

概述最大路径和

首先是树的建立

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=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

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

 

总结

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

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