124. Binary Tree Maximum Path Sum
dfs
Given anon-emptybinary 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 containat least one nodeand does not need to go through the root.
Example 1:
Input:
[1,2,3]
1
/ \
2
3
Output:
6
Example 2:
Input:
[-10,9,20,null,null,15,7]
-10
/ \
9
20
/ \
15 7
Output:
42
分析
无论任何情况, 必须要包含根节点!!!! return = root+max(left,right), result = root+left+right
处理负值:
使用
max(dfs(node.left), 0)
确保不考虑负贡献这样能正确处理所有节点值为负的情况
路径计算:
path_sum
计算当前节点作为最高点的完整路径和res
记录全局最大值
返回值:
只能返回当前节点加上左或右子树的最大贡献值
这样保证返回的是单边路径
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
ans = float("-inf")
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.dfs(root)
return self.ans
def dfs(self,root):
if not root:
return 0
left = max(0,self.dfs(root.left))
right = max(0,self.dfs(root.right))
self.ans = max(self.ans,left+right+root.val)
return max(0,left+root.val,right+root.val)
Last updated
Was this helpful?