题目
摘自LeetCode124
解题方法
选择了一道LeetCode上难度为困难的递归求解的算法题。
算法如下：
- 当前遍历的节点为root，root是否在最大路径中，需要计算root.val值与左右子树返回的路径的和，并且与现在最大路径和进行比较，如果大于，则保存；
如下图1，设root节点为20，计算黄色节点的和，判断是否是最大的路径和。
图1
- 递归返回值不是包括root的最大路径和，而是root.val值与左右子树路径的大值的和；
递归返回值如下图2，同样设root节点为20，返回值为粉色节点和，20+15=35（因为15 > 7）
图2
3.如果节点是空，返回0。同时如果左右子树路径是负值，不计入到最大路径中（因为加负值只会让路径和更小）。
代码
public int maxPathSum(TreeNode root) {
//定义长度为1的数组存储最大路径和
int[] result = {Integer.MIN_VALUE};
maxPathSumHelper(root, result);
return result[0];
}
//递归寻找最大路径和
private int maxPathSumHelper(TreeNode root, int[] result){
//空节点返回0
if(null == root){
return 0;
}
//递归左子树
int leftMaxPath = maxPathSumHelper(root.left, result);
//如果最大路径大于0，则保留；小于0，则保留0
leftMaxPath = leftMaxPath > 0 ? leftMaxPath : 0;
//递归右子树
int rightMaxPath = maxPathSumHelper(root.right, result);
//如果最大路径大于0，则保留；小于0，则保留0
rightMaxPath = rightMaxPath > 0 ? rightMaxPath : 0;
//新的路径和是当前节点加上左右子树的路径
int newMaxPath = leftMaxPath + rightMaxPath + root.val;
//如果大于当前的最大路径和，则保留
result[0] = newMaxPath > result[0] ? newMaxPath : result[0];
//返回值是当前节点值与左右子树路径的大值的和
return root.val + Math.max(leftMaxPath, rightMaxPath);
}
