题目:路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

 

思想:

后序遍历,我们把问题分成两种情况

情况一:路径包括当前结点(父节点)

我们需要将左右子树的路径信息传回,返回的值是子树中最大的那一边加上父节点的和,注意如果出现负值则舍弃不加入。

返回一边的原因是,路径不能走回头路。

情况二:路径不包括当前结点(父节点)

我们只需要返回左右子树的最大路径即可。

func maxPathSum(root *TreeNode) int {
	var max int = 0
	var dfs func(root *TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil{
			return 0
		}
		left := dfs(root.Left)
		right := dfs(root.Right)
		curmax := root.Val+left+right  //情况二,我们先计算子树的路径大小,curmax
		if curmax>max{
			max = curmax  //如果比目前最大的还要大,则取而代之
		}
		var outmax int  //情况一,如果考虑父结点,我们计算出能给父结点提供最大路径的那一边outmax,不同时使用两边是为了不重复路径
		if left>right{
			outmax = root.Val+left
		}else{
			outmax = root.Val+right
		}
		if outmax>0 {
			return outmax  //如果是正值,则返回给父结点,等父结点调用更新max
		}
		return 0  //如果左右子树都提供负值,都舍弃返回父结点一个0值
	}
	dfs(root)
	return max
}

题目来源：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum