解法一：（递归）考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
具体而言，该函数的计算如下。
- 空节点的最大贡献值等于 0。
- 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {int maxSum = Integer.MIN_VALUE; // 全局变量记录最大值public int maxPathSum(TreeNode root) {maxRoot(root);return maxSum;}public int maxRoot(TreeNode root){// 计算root节点的最大贡献值if(root==null){return 0;}// 左右节点我们只取大于0的节点(不取负数，以得到maxSum的最大值)int left = Math.max(maxRoot(root.left),0);int right = Math.max(maxRoot(root.right),0);// 更新全局最大值int newPath = root.val + right + left;maxSum = Math.max(maxSum, newPath);// 返回值return root.val + Math.max(right,left);}
}
注意：
- 递归函数
maxRoot的作用为计算root节点的最大贡献值 - 全局变量
maxSum的作用为记录最大路径和 - 递归左右节点时，我们只取大于0的节点(不取负数，以得到maxSum的最大值)：
int left = Math.max(maxRoot(root.left),0); - 更新最大值时，要考虑当前节点值+左节点最大贡献值+右节点最大贡献值，然后和maxSum取最大值
- 返回值为：
root.val + Math.max(right,left)