维护一个全局最大路径和，找出每个节点的最大贡献值，具体细节看代码。
参考链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/solutions/297005/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/

/*** 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 {private int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {// int temp = maxGain(root);maxGain(root);return maxSum;}private int maxGain(TreeNode root) { // 贡献值指的是从当前root出发if (root == null) return 0;// 左右子树最大贡献值int leftGain = Math.max(maxGain(root.left), 0);int rightGain = Math.max(maxGain(root.right), 0);// 计算路径的时候应该将目前节点root作为中间节点，联通两端int pricePath = leftGain + rightGain + root.val;maxSum = Math.max(pricePath, maxSum);// 返回当前节点的最大贡献值，因为root不能重复，一次只能选择其中一边return root.val + Math.max(leftGain, rightGain);}
}