## Tree - 124. Binary Tree Maximum Path Sum

Published on with 0 views and 0 comments

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

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
// import "math"

func maxPathSum(root *TreeNode) int {
if root == nil {
return math.MinInt32
}

var res = math.MinInt32
dfs(root, &res)
return res
}

func dfs(node *TreeNode, res *int) int {
if node == nil {
return 0
}

left := max(dfs(node.Left, res), 0)
right := max(dfs(node.Right, res), 0)

// 记录最大路径和
*res = max(*res, node.Val + left + right)

return node.Val + max(left, right)
}

func max(i, j int) int {
if i > j {
return i
}
return j
}
``````