# 124.H 二叉树中的最大路径和

> Problem: [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/)

\[TOC]

## 思路

定义一个函数maxGain用来计算某个某个节点的最大贡献值，最大贡献值是指以该节点为起点的最大路径和。

对于每个节点来说，子节点的贡献值`childGain=max(maxGain(root.child), 0)`，因为如果子节点的贡献值小于`0`，可以不取这个子节点。当前节点的最大共享值则等于`root.Val + max(leftGain, rightGain)`，即当前节点加上最大贡献值的路径。经过该节点的路径和则等于`leftGain+root.Val+rightGain`

## Code

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt
	var maxGain func(root *TreeNode) int
	maxGain = func(root *TreeNode) int {
		if root == nil {
			// impossible case
			return 0
		}

		leftGain := max(maxGain(root.Left), 0)
		rightGain := max(maxGain(root.Right), 0)

		maxSum = max(maxSum, leftGain+root.Val+rightGain)
		return root.Val + max(leftGain, rightGain)
	}

	maxGain(root)
	return maxSum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
```