脚本宝典收集整理的这篇文章主要介绍了leetcode-124-Binary Tree Maximum Path Sum,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目描述:
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child
connections. The path must contain at least one node and does not need
to go through the root.
举例:
Given the below binary tree,
1
/
2 3
Return 6.
题目分析: 找从任意节点出发的任意路径的最大长度。 每个node都有可能是其他路径上的node,这种情况要max(left,right)。如此循环。 每个node都有可能作为中心node,此时要max(左侧之前的路径最长长度,左侧之前的路径最长长度,此node为中心时候的长度)
将这个分析单元递归封装,即可实现目标。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def dfs(self,node):
ls = rs = None
lmv = rmv = 0
if node.left:
lmv,ls=self.dfs(node.left)
lmv=max(lmv,0)
if node.right:
rmv,rs=self.dfs(node.right)
rmv=max(rmv,0)
# print(lmv,rmv,ls,rs)
mv=node.val+max(lmv,rmv)
sv=node.val+lmv+rmv
# mv=node.val
trans_list=[elem for elem in [sv,ls,rs] if elem]
if not trans_list:
trans_list=[0]
return mv,max(trans_list)
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return
mv,smv=self.dfs(root)
return max(mv,smv)
if __name__=='__main__':
tn=TreeNode(2)
tn1=TreeNode(-1)
tn2=TreeNode(-2)
tn.left=tn1
tn.right=tn2
以上是脚本宝典为你收集整理的leetcode-124-Binary Tree Maximum Path Sum全部内容,希望文章能够帮你解决leetcode-124-Binary Tree Maximum Path Sum所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。