124. Binary Tree Maximum Path Sum

Intuitively, we can use recursive method to solve the problem. In order to get the max path sum, we must consider every node in the tree.

The final path must consist of three parts: one node as root (necessary), an Up To Down Path originated from its left child (optional) and an Up To Down Path originated from its right child (optional). Here, the Up to Down Path denotes a sub path originated from a node to its leaf.

We use leftMax to denote the max up to down path sum originated from the left child of a node and rightMax to denote the max up to down path sum originated from the right child of a node. Then the max path sum of a node n is n.val + Math.max(leftMax, 0) + Math.max(rightMax, 0). Apparently, if leftMax or rightMax is no greater than zero, then we don't need them and that's why they are optional.

After processing a node, we return its max up to down path sum (not max path sum), i.e., n.val + Math.max(Math.max(leftMax, 0), Math.max(rightMax, 0)).

As we can see, the key point of this problem is processing current node to get max path sum while returning max up to down path sum after processing the node. It is an important idea for solving complex tree problems: processing a problem and return the result of another problem.

int result = Integer.MIN_VALUE;
    
public int maxSum(TreeNode root) {	
    if( root == null )
	return 0;
    int leftMax = Math.max(0, maxSum(root.left));
    int rightMax = Math.max(0, maxSum(root.right));
    result = Math.max(result, root.val + leftMax + rightMax);
    return root.val + Math.max(leftMax, rightMax);
}

public int maxPathSum(TreeNode root) {
    if( root == null )
	return 0;
    else {
	maxSum(root);
	return result;
    }
}