描述
给出一棵二叉树,寻找一条路径使其路径和最大,路径可以在任一节点中开始和结束(路径和为两个节点之间所在路径上的节点权值之和)
样例
给出一棵二叉树:
1
/ \
2 3
返回 6
代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: An integer
"""
def maxPathSum(self, root):
# write your code here
self.maxPath = root.val
self.Dfs(root)
return self.maxPath
def Dfs(self, root):
# TODO: write code...
if root is None:
return 0
left = max(0, self.Dfs(root.left))
right = max(0, self.Dfs(root.right))
leap = left + root.val + right
if leap > self.maxPath:
self.maxPath = leap
return max(left + root.val, right + root.val)
仔细想,发现从任意节点开始和结束,其实就意味最大路径和可以选择子树的根节点作为计算路径和的开始,则
leap = left + root.val + right
if leap > self.maxPath:
self.maxPath = leap
就表达出了最大路径可以是任意子树的经过根节点的最大路径和。
网友评论