比較有意思的題，不過算不上hard tag.
這里我們記錄一個max(用int[]是為了不使用global)來記錄max path sum(可以是任意node為起點終點蝗茁，整條path大于等于一個node就可以胳喷。也要注意這里的node值可以是負(fù)數(shù)。
helper函數(shù)的定義是以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;
}
}
