leetcode 124.二叉树中的最大路径和 golang实现
// 初版
var IntMax = int(^uint(0) >> 1)
func maxPathSum(root *TreeNode) int {
if root == nil{
return 0
}
var max = ^IntMax
maxPathSumHelp(root, &max)
return max
}
// 本函数获取的是节点可提供的最大路径和并不是本节点的最大路径和 而是节点的半个分支 ：即左分支和右分支和本节点的最大值
func maxPathSumHelp(root *TreeNode, max *int)int{
var left int
var right int
var rootMax int // 统计本节点的最大路径和
// 获取左子节点可提供的最大路径和
if root.Left != nil{
left = maxPathSumHelp(root.Left, max)
}
// 获取右子节点可提供的最大路径
if root.Right != nil{
right = maxPathSumHelp(root.Right, max)
}
// 如果大于0
if left > 0{
// 本节点的最大路径和+left
rootMax = rootMax + left
}
if right > 0{
// 本节点的最大路径和+left
rootMax = rootMax + right
}
rootMax = rootMax + root.Val // rootMax 则为通过本节点的最大路径和
*max = Max(*max, rootMax) // 将rootMax 和 max的较大值赋值给max
// 返回本节点可提供给父节点的最大路径 如果left和right都小于0 则值返回root.Val 否则返回较大的分支+root.Val
if Max(left, right) > 0{
return Max(left, right) + root.Val
}else{
return root.Val
}
}
// 第二版
func Max(a, b int) int {
if a >= b {
return a
} else {
return b
}
}
func MaxPathSum(root *TreeNode) int {
var intMax = int(^uint(0) >> 1)
var intMin = ^intMax
var max = intMin // max 初始值为int 的最小值， 因为在递归时 有可能会有零值
DoMaxPathSum(root, &max)
return max
}
func DoMaxPathSum(root *TreeNode, max *int) int{
var maxL int
var maxR int
var maxRoot int
if root == nil{
return 0
}
maxL = Max(DoMaxPathSum(root.Left, max), 0) // 子树如果为负值 则没有必要经过了
maxR = Max(DoMaxPathSum(root.Right, max), 0)
maxRoot = maxL + maxR + root.Val // 当前节点能贡献的最大值
*max = Max(*max, maxRoot)
return root.Val + Max(maxL, maxR) // 必须经过根节点 否则路径会断
}