二叉树中的最大路径和（LeetCode124--二叉树中的最大路径和）

题目

摘自LeetCode124

解题方法

选择了一道LeetCode上难度为困难的递归求解的算法题。
算法如下：

1. 当前遍历的节点为root，root是否在最大路径中，需要计算root.val值与左右子树返回的路径的和，并且与现在最大路径和进行比较，如果大于，则保存；

如下图1，设root节点为20，计算黄色节点的和，判断是否是最大的路径和。

图1

2. 递归返回值不是包括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);
}