1.问题描述
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例1
示例2
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
难度等级
困难
题目链接
2.解题思路
这道求最大路径和的问题，我们简单观察一下可以发现，最大的路径和是由左子树的一条单方向路径+当前的节点值+右子树的一条单方向路径组成，我这里的单方向路径的意思是不从树的最顶层根节点拐弯，所以我们这里要用到的遍历方法是后序遍历，先求到左右子树所能提供的单方向最大路径，才能计算最大路径。
我们可以用一个全局的变量来存储最大路径，便于每一次获得新路径之后的更新。
int max = Integer.MIN_VALUE;
因为我们的主方法需要返回最大路径，而我们求解过程的后序遍历要返回的是单方向的最大路径，所以我们后续遍历的操作要单独用一个方法来完成，不能直接用主方法来完成。
//计算节点路径和
public int rootPathSum(TreeNode root)
首先，确定递归的结束条件，如果根节点为空，直接返回0。
//如果节点为空，直接返回0
if(root == null){
return 0;
}
接着，补充单层的递归逻辑。因为我们需要用后续遍历来遍历二叉树，所以第一步是调用递归方法获取左右子树的最大单方向路径和。这里我们可以做一个小优化，我们可以将得到的路径和与0进行比较，如果路径和小于0，我们就将路径和当做0，因为我们是要求最大的路径和，如果子树的路径为负数，那最大路径和不可能包含这条和为负数的路径的，当做0相当于我们不走这条路径了。
//寻找左子树中最大路径和
int left = Math.max(rootPathSum(root.left),0);
//寻找右子树中最大路径和
int right = Math.max(rootPathSum(root.right),0);
然后，更加我们一开始分析的，最大的路径和是由左子树的一条单方向路径+当前的节点值+右子树的一条单方向路径组成，求出以当前节点为最顶层根节点的最大路径和，并于现有的最大值进行比较，更新现有的最大值。
//更新最大值
max = Math.max(left + right + root.val,max);
后序遍历方法的最后一步，就是将左右单方向路径之中最大的那个路径，加上根节点的值，作为再上一层的根节点的单方向路径返回。
//返回当前节点所能给上层节点提供的最大路径和
return root.val + Math.max(left,right);
最后，在主方法调用我们的后序遍历方法，并将最大值返回即可。
//计算节点路径和
rootPathSum(root);
return max;
3.代码展示
/**
* 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 max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
//计算节点路径和
rootPathSum(root);
return max;
}
//计算节点路径和
public int rootPathSum(TreeNode root){
//如果节点为空，直接返回0
if(root == null){
return 0;
}
//寻找左子树中最大路径和
int left = Math.max(rootPathSum(root.left),0);
//寻找右子树中最大路径和
int right = Math.max(rootPathSum(root.right),0);
//更新最大值
max = Math.max(left + right + root.val,max);
//返回当前节点所能给上层节点提供的最大路径和
return root.val + Math.max(left,right);
}
}
4.总结
这道题难度其实还行，关键是要分清楚两个最大和，一个是最大的路径和，一个子树的单方向最大路径和，最大的路径和是由左子树的一条单方向路径+当前的节点值+右子树的一条单方向路径组成。弄清除两个最大和之间的关系后，这道题基本就迎刃而解了。好了，这道题就简单啰嗦到这里，祝大家刷题愉快~
