今天就跟大家聊聊有关怎样分析python二叉树的最大路径和，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
计算
安全
数据库
网络和加速
企业服务
输入: [1,2,3] 1 / \ 2 3输出: 6示例 2:
输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7输出: 42解题思路：
对于二叉树问题优先想到递归，因为划分子问题比较容易，最大路径和隐含问题是路径连续
1，由于可能含根，可能不含根，所以最大和为
max(根的值，左分支含根最大和，左分支含根最大和＋根，右分支含根最大和，右分支含根最大和＋根，左分支含根最大和＋根＋右分支含根最大和，左分支不含根最大和，右分支不含根最大和)
2，上述问题包含含根（单边）最大和子问题，求解为
max（根的值，根的值＋左含根最大和，根的值＋右含根最大和）
注意不包含：左含根最大和＋根的值＋右含根最大和，因为路线不能有分叉
代码如下
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func maxPathSum(root *TreeNode) int { if root==nil{ return 0 } if root.Left!=nil && root.Right!=nil{ lr:=maxPathSumRoot(root.Left) rr:=maxPathSumRoot(root.Right) l:=maxPathSum(root.Left) r:=maxPathSum(root.Right) a:=[]int{root.Val,root.Val+lr,root.Val+rr,lr,rr,root.Val+lr+rr,l,r} return max(a) }else if root.Left!=nil { lr:=maxPathSumRoot(root.Left) l:=maxPathSum(root.Left) a:=[]int{root.Val,root.Val+lr,lr,l} return max(a) }else if root.Right!=nil{ rr:=maxPathSumRoot(root.Right) r:=maxPathSum(root.Right) a:=[]int{root.Val,root.Val+rr,rr,r} return max(a) } return root.Val}func max(arr []int) int{ max:=-1<<31 for i:=0;i<len(arr);i++{ if max<arr[i]{ max=arr[i] } } return max}func maxPathSumRoot(root *TreeNode) int { if root==nil{ return 0 } l:=maxPathSumRoot(root.Left) r:=maxPathSumRoot(root.Right) return max([]int{l+root.Val,r+root.Val,root.Val}) }看完上述内容，你们对怎样分析python二叉树的最大路径和有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4634853
