二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点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

关键点：设置全局变量记录最大值，递归调用，在递归里做两件事，递归计算左右子节点的最大贡献值，根据返回的最大贡献值返回当前节点和左/右节点(谁大取谁, 如果都小于0，则取0)的和记为当前节点的最大贡献值计算出一个最大路径和，根节点+左最大贡献值+右最大贡献值，和全局最大路径取大者

Integer maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode root) { if (root == null) { return 0; } // 递归计算左右子节点的最大贡献值， 只有在最大贡献值大于0时才会选取对应子节点 int leftGain = Math.max(maxGain(root.left), 0); int rightGain = Math.max(maxGain(root.right), 0); // 计算新的最大贡献值 根节点+左子节点的最大贡献值+右子节点的最大贡献值 int newSum = root.val + leftGain + rightGain; // 和全局最大贡献值取大者 maxSum = Math.max(maxSum, newSum); // 返回节点的最大贡献值 return root.val + Math.max(leftGain, rightGain); }