package BinaryTree
import "math"
type maxPathSumRet struct {
maxSum, maxSumWithRoot int
}
func maxPathSum(root *TreeNode) int {
return maxPathSumFunc(root).maxSum
}
func maxPathSumFunc(node *TreeNode) maxPathSumRet {
if node == nil {
return maxPathSumRet{
maxSumWithRoot: 0,
maxSum: math.MinInt,
}
}
leftRet := maxPathSumFunc(node.Left)
rightRet := maxPathSumFunc(node.Right)
curMaxSumWithRoot := max(node.Val, node.Val+leftRet.maxSumWithRoot, node.Val+rightRet.maxSumWithRoot)
curMaxSum := max(leftRet.maxSum, rightRet.maxSum, curMaxSumWithRoot, node.Val+leftRet.maxSumWithRoot+rightRet.maxSumWithRoot)
return maxPathSumRet{
maxSumWithRoot: curMaxSumWithRoot,
maxSum: curMaxSum,
}
}