start from current node, get left node’s max path sum, right node’s max path sum max path sum of the tree with current node as root is
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return maxSum;
}
private int helper(TreeNode root) {
if (root == null) return 0;
int leftGain = Math.max(helper(root.left), 0);
int rightGain = Math.max(helper(root.right), 0);
// continue the same path
int sameMax = Math.max(leftGain + root.val, rightGain + root.val);
// or start a new path
maxSum = Math.max(leftGain + root.val + rightGain, maxSum);
return sameMax;
}
}