015.二叉树中的最大路径和

• 124.二叉树中的最大路径和
  • 递归

二叉树中的最大路径和 - 递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
var ans int
 
func maxPathSum(root *TreeNode) int {
	ans = math.MinInt
	getSum(root)
	return ans
}
 
// 计算二叉树中的 root 节点的最大贡献值
func getSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
 
	// 递归计算左右子节点的最大贡献值
	// 只有在最大贡献值大于 0 时，才会选取对应子节点
	left := max(getSum(root.Left), 0)
	right := max(getSum(root.Right), 0)
 
	// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
	res := root.Val + left + right
	if res > ans {
		ans = res
	}
 
	// 返回节点的最大贡献值
	return root.Val + max(left, right)
}