For each node, there may be several conditions:
1. root.left <0 and root.right <0, the max will be root.val
2.root.left or root.right < 0, the max will be root.val + root.left/right
3.no one <0, max will be root.val + root.left + root.right
However, for nodes except the root, what we return is not root.val + both, instead, we only choose one substree + root.val so that we avoid branching. What we return is only for calculating the max of the parent node.
class Solution {
int result = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return result;
}
public int helper(TreeNode root){
if(root == null) return 0;
int first = Math.max(0, helper(root.left));
int second = Math.max(0,helper(root.right));
result = Math.max(result, first + second + root.val); // It's possible that the max is any substree node, so we calculate the total value every step
return root.val + Math.max(first,second); // however, for calculating the parent, we only return the max substree+node.val inorder to avoid branches
}
}
