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:
Example 2:
分析
无论任何情况, 必须要包含根节点!!!! return = root+max(left,right), result = root+left+right
处理负值:
使用
max(dfs(node.left), 0)
确保不考虑负贡献这样能正确处理所有节点值为负的情况
路径计算:
path_sum
计算当前节点作为最高点的完整路径和res
记录全局最大值
返回值:
只能返回当前节点加上左或右子树的最大贡献值
这样保证返回的是单边路径
Last updated
Was this helpful?