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

Problem: 124. 二叉树中的最大路径和

[TOC]

思路

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

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

Code

/**
 * 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
}