比较有意思的题，不过算不上hard tag.
这里我们记录一个max(用int[]是为了不使用global)来记录max path sum(可以是任意node为起点终点，整条path大于等于一个node就可以。也要注意这里的node值可以是负数。
helper函数的定义是以root为最高根所能找到的max sum path的sum值，我么分别求出以root的左孩子和右孩子为最高点所能找到的max sum path的sum.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
1
/ \
2 3
/ \ / \
5 3 9 4
max[0]: maxPathSum
helper method 1.returns path sum that can be extended to the parent of input root 5-2 can, 5-2-3 can not
2.computes max path sum with higest node the input root (left + right + root.val) and update the max path sum
use max(0, helper(root.left, max)) to calculate left and right to avoid change codes when l,r < 0
*/
class Solution {
public int maxPathSum(TreeNode root) {
if (root == null){
return 0;
}
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
helper(root, max);
return max[0];
}
private int helper(TreeNode root, int[] max){
if (root == null){
return 0;
}
int left = Math.max(0,helper(root.left, max));
int right = Math.max(0,helper(root.right, max));
max[0] = Math.max(max[0],left + right + root.val);
return Math.max(left, right) + root.val;
}
}
