1、题目描述
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和?是路径中各节点值的总和。给你一个二叉树的根节点?root?，返回其?最大路径和?。
?
?2、算法分析
首先，不要过分纠结递归的细节。课后可以一起探讨。
路径每到一个结点，有3种选择：1、停留在当前结点 2、走到左子树结点 3、走到右子树结点。当走到子结点的时候，又会面临着3种选择，递归就是用来处理规模不一样，但是过程相同的问题。
从父节点下来的路径，有三种情况：
① 路径停留在当前根节点，那么val：root.val
② 路径进入root的左子树，那么val：root.val + dfs(root.left)
③ 路径进图root的右子树，那么val：root.val + dfs(root.right)
那么三者的最大收益：root.val + Math.max(dfs(root.left),dfs(root.right))
注意：
（1）一条从父节点延伸下来的路径，不能走入左子树又掉头走右子树，不能两头收益，路径会重叠。
（2）当遍历到
null节点时，null 子树提供不了收益，返回 0。（3）如果某个子树 dfs 结果为负，走入它，收益不增反减，该子树应被忽略，杜绝选择走入它的可能，让它返回 0，像null一样，如同砍掉。、
子树中的内部路径要包含根节点：
由题意可知，最大路径和可能产生于局部子树中，如下图左一。所以每递归一个子树，都求一下当前子树内部的最大路径和，如下图右一的绿色数值，从中比较出最大的。
注意: 一个子树内部的路径，要包含当前子树的根节点。如果不包含，那还算什么属于当前子树的路径，那就是当前子树的子树的内部路径了。
所以，一个子树内部的最大路径和 = 左子树提供的最大路径和 + 根节点值 + 右子树提供的最大路径和。即 dfs(root.left) + root.val + dfs(root.right)
?
?
3、代码实现
class Solution {
int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return result;
}
// 函数功能：返回当前节点能为父亲提供的贡献，需要结合上面的图来看！
private int dfs(TreeNode root) {
// 如果当前节点为叶子节点，那么对父亲贡献为 0
if(root == null) return 0;
// 如果不是叶子节点，计算当前节点的左右孩子对自身的贡献left和right
int left = dfs(root.left);
int right = dfs(root.right);
// 更新最大值，就是当前节点的val 加上左右节点的贡献。
result = Math.max(result, root.val + left + right);
// 计算当前节点能为父亲提供的最大贡献，必须是把 val 加上！
int max = Math.max(root.val + left, root.val + right);
// 如果贡献小于0的话，直接返回0即可！
return max < 0 ? 0 : max;
}
}