二叉树最大路径和golang版本

二叉树最大路径和golang版本

//此常量是根据补码，首位为0，其它位是1原理进行定义的
const INT_MAX = int(^uint(0) >> 1)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 初版
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 {

		rootMax = rootMax + right
	}

	rootMax = rootMax + root.Val
	*max = Max(*max, rootMax)
	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
	}
	return b
}

//迭代版本
func MaxPathSum(root *TreeNode) int {
	var intMax = int(^uint(0) >> 1)
	var intMin = ^intMax
	var max = intMin
	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)
}

func Max(a, b int) int {
	if a >= b {

		return a
	}
	return b
}