0124. Binary Tree Maximum Path Sum

# 124. Binary Tree Maximum Path Sum#

## 题目 #

Given a non-empty 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.

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
``````

## 解题思路 #

• 给出一个二叉树，要求找一条路径使得路径的和是最大的。
• 这一题思路比较简单，递归维护最大值即可。不过需要比较的对象比较多。`maxPathSum(root) = max(maxPathSum(root.Left), maxPathSum(root.Right), maxPathSumFrom(root.Left) (if>0) + maxPathSumFrom(root.Right) (if>0) + root.Val)` ，其中，`maxPathSumFrom(root) = max(maxPathSumFrom(root.Left), maxPathSumFrom(root.Right)) + root.Val`

## 代码 #

``````
package leetcode

import "math"

/**
* 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
}
max := math.MinInt32
getPathSum(root, &max)
return max
}

func getPathSum(root *TreeNode, maxSum *int) int {
if root == nil {
return math.MinInt32
}
left := getPathSum(root.Left, maxSum)
right := getPathSum(root.Right, maxSum)

currMax := max(max(left+root.Val, right+root.Val), root.Val)
*maxSum = max(*maxSum, max(currMax, left+right+root.Val))
return currMax
}

``````

Nov 25, 2022